Smallest path in graph theory (social network analysis)

This is the scenario: There is an undirected graph with n nodes and e edges, all nodes are connected.

The question in the scenario: Every node can be considered as a person in a social network that shares or reads a content. It means that if A is connected to B, C and D, if A shares a content with the network, it will reach directly BCD. It means that to reach all the nodes in the network, it's just necessary that they are adjacent to a node which shared the content.

Q1: is there a way to find the best starting point to reach the entire network? Q2: is there a way to find a smallest path from that point?

I've already looked at salesman problem and prim'algorithm.

Thank开发者_Python百科s!

---

The wikipedia page on Centrality describes several different forms of centrality in a graph, and has links to algorithms for some of them.

---

Raising the adjacency matrix of the network to the nth power gives you the number of walks of length n between two verticies i,j (represented by the ij-th element of the matrix). The first non zero value of x(i,j) will tell you how far apart they are with respect to walks. If you're looking for the best node to reach the whole network, then you could just look for the first instance of a row (or column) of the matrix which has all non zero values whilst increasing n.

Obviously this isn't practical with huge networks...

Otherwise you could apply Dijkstra's algorithm.

---

Closeness Centrality is a ranking of each individual node and can be thought of as a measure of how "close a node is to the center of a network". So a node with a high closeness centrality value is positioned in the network such that it takes this node a shorter number of hopes (on average) to reach all other nodes in the network. So for Q1 above, the node(s) with the highest closeness could be interpreted to be in the best position to reach all other nodes with a minimum number of hops between nodes on the way. For Q2, the "smallest path" can be considered the smallest average path to all nodes in the network.