图论中的最小路径（社交网络分析）
这是场景： 有一个无向图，有n个节点和e条边，所有节点都是连通的。
场景中的问题： 每个节点都可以被视为社交网络中共享或阅读内容的人。这意味着如果A连接到B、C和D，如果A与网络共享内容，它将直接到达BCD。这意味着要到达网络中的所有节点，只需它们与共享内容的节点相邻即可。
Q1：有没有办法找到到达整个网络的最佳起点？ Q2：有没有办法找到从该点开始的最小路径？
我已经研究过推销员问题和原始算法。
谢谢！
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.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
关于中心性的维基百科页面描述了图中几种不同形式的中心性，并提供了算法的链接其中一些。
The wikipedia page on Centrality describes several different forms of centrality in a graph, and has links to algorithms for some of them.
将网络的邻接矩阵求 n 次方即可得出两个顶点 i,j 之间长度为 n 的路径数（由矩阵的第 ij 个元素表示）。 x(i,j) 的第一个非零值将告诉您它们相对于行走的距离有多远。如果您正在寻找到达整个网络的最佳节点，那么您可以只查找矩阵的行（或列）的第一个实例，该实例在增加 n 的同时具有所有非零值。
显然这对于巨大的网络来说是不切实际的......
否则你可以应用 Dijkstra 算法。
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.
紧密度中心性是每个单独节点的排名，可以被认为是衡量“紧密程度”的指标。节点是网络的中心”。因此，具有高接近中心度值的节点位于网络中，使得该节点需要较少的希望（平均）来到达网络中的所有其他节点。因此，对于上面的 Q1，具有最高紧密度的节点可以被解释为处于到达所有其他节点的最佳位置，并且节点之间的跳数最少。对于Q2，“最小路径”可以被认为是到网络中所有节点的最小平均路径。
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.