Finding communities in linear time: a physics approach
Finding communities in linear time: a physics approach
复制标题
DOI：
10.1140/epjb/e2004-00125-x
复制
发表时间：
2004-03-01
影响因子：
1.6
通讯作者：
Huberman, BA
中科院分区：
文献类型：
--
作者：
Wu, F;Huberman, BA
我们提出了一种方法，允许在任意大小的图中发现与它们的大小成线性比例的社区。这种方法避免了切边，并且基于跨网络电压降的概念，无论所涉及的图的复杂性如何，这种概念都是直观且易于解决的。我们还展示了该算法如何允许快速发现给定节点周围的社区，而无需从图中提取所有社区。
We present a method that allows for the discovery of communities within graphs of arbitrary size in times that scale linearly with their size. This method avoids edge cutting and is based on notions of voltage drops across networks that are both intuitive and easy to solve regardless of the complexity of the graph involved. We additionally show how this algorithm allows for the swift discovery of the community surrounding a given node without having to extract all the communities out of a graph.