Computing the Diameters of Huge Social Networks
Computing the Diameters of Huge Social Networks
复制标题
计算大型社交网络的直径
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
B. Wu
中科院分区：
文献类型：
--
作者：
Ting;Mei;Wei;B. Wu
图的直径是所有结点对之间的最大距离。用传统的方法确定一个图的直径需要O(M)个时间，其中n是节点数，m是边数。社交网络可以被建模为一张图。随着社交网络的迅速扩张，一个社交网络中的节点数量可能达到数亿个。在这篇文章中，我们提出了一种计算大型无向无权图直径的新方法。最坏情况下的时间复杂度仍为O(MN)。在实际应用中，特别是对于社会网络图，运行时间为O(M)。我们的方法是基于BFS的，选择合适的节点作为BFS过程的起始节点是计算直径时最重要的问题。我们展示了如何以较小的代价选择好的节点。
The diameter of a graph is the maximum distance among all pairs of nodes. Determining the diameter of a graph in the tradition way costs O(mn) time, where n is the number of nodes and m is the number of edges. A social network can be modelled as a graph. With the rapid expansion of social networks, the number of nodes in a social network could be hundreds of millions. In this paper, we propose a new approach for computing the diameters of large undirected unweighted graphs. The worst case time complexity is still O(mn). In practice, especially for social network graphs, the running time is O(m). Our approach is based on BFS to select a proper node as the starting node of a BFS process is the most important issue when computing the diameter. We show how to choose the good nodes with small cost.