1] School of Computer Science and Technology, Tianjin University, Tianjin 300072, China [2] State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China.
Sci Rep. 2013 Oct 21;3:2993. doi: 10.1038/srep02993.
Community detection is important for understanding networks. Previous studies observed that communities are not necessarily disjoint and might overlap. It is also agreed that some outlier vertices participate in no community, and some hubs in a community might take more important roles than others. Each of these facts has been independently addressed in previous work. But there is no algorithm, to our knowledge, that can identify these three structures altogether. To overcome this limitation, we propose a novel model where vertices are measured by their centrality in communities, and define the identification of overlapping communities, hubs, and outliers as an optimization problem, calculated by nonnegative matrix factorization. We test this method on various real networks, and compare it with several competing algorithms. The experimental results not only demonstrate its ability of identifying overlapping communities, hubs, and outliers, but also validate its superior performance in terms of clustering quality.
社区发现对于理解网络很重要。先前的研究观察到社区不一定是不相交的，它们可能会重叠。人们还一致认为，一些异常点顶点不参与任何社区，而社区中的一些集线器可能比其他集线器扮演更重要的角色。这些事实中的每一个都在先前的工作中被独立地解决了。但是，据我们所知，还没有一种算法可以同时识别这三种结构。为了克服这一限制，我们提出了一种新的模型，其中顶点通过它们在社区中的中心度来衡量，并将重叠社区、集线器和异常点的识别定义为一个优化问题，通过非负矩阵分解来计算。我们在各种真实网络上测试了这种方法，并将其与几种竞争算法进行了比较。实验结果不仅证明了它识别重叠社区、集线器和异常点的能力，还验证了它在聚类质量方面的优越性能。
