Community Detection in Scale-Free Networks using Edge Weight and Modularity Optimization Method
Community Detection in Scale-Free Networks using Edge Weight and Modularity Optimization Method
复制标题
DOI：
10.1527/tjsai.30.84
复制
发表时间：
2015-01
影响因子：
--
通讯作者：
Sorn Jarukasemratana;T. Murata
中科院分区：
文献类型：
--
作者：
Sorn Jarukasemratana;T. Murata
在本文中，我们提出了一个两步算法来执行社区检测无标度网络。无标度网络的一个主要特征是节点度分布服从幂律。然而，在我们自己的实验中，我们遇到了另一种无标度网络的子类型，我们称之为“混合无标度网络”。有些社区有枢纽节点，节点度服从幂律分布;有些社区没有枢纽节点，节点度服从正态分布。对于混合无标度网络，由于无标度特性，没有专门针对无标度设计的方法将有困难。同时，由于某些社区节点度服从正态分布，基于无标度的方法也会遇到困难。在这项研究中，我们提出了一个社区检测算法，可以工作在网络中，同时包含两种类型的社区。我们的方法可以正确处理这种情况，因为我们的算法迭代地执行无标度和非无标度方法。为了评估我们的方法，我们使用NMI归一化互信息来衡量我们在合成和真实世界数据集上的结果，并与无标度和非无标度社区检测方法进行比较。结果表明，该方法在混合无标度网络和无标度网络上的性能优于基线方法，而在正态度分布网络上的性能相当。
In this paper, we propose a two-step algorithm to perform a community detection in scale-free networks. One of the main characteristics of scale-free networks is that node degree distribution follows a power law. However, during our own experiments, we encountered another sub-type of scale-free networks which we call “mixed scalefree networks”. Some communities have hub nodes and node degree follows power law distribution, while some communities do not have hub nodes and node degree follows normal distribution. For mixed scale-free networks, methods that do not specifically design for scale-free will have difficulties because of the scale-free properties. At the same time, scale-free based methods will have difficulties because some communities have node degree follows normal distribution. In this research, we propose a community detection algorithm that can work on networks that contain both types of communities at the same time. Our method can handle this case correctly because our algorithm performs both scale-free and non scale-free approaches iteratively. To evaluate our method, we use NMI Normalized Mutual Information to measure our results on both synthetic and real-world datasets comparing with both scalefree and non scale-free community detection methods. The results show that, our method outperforms baseline methods on mixed scale-free networks and scale-free networks while performs equally on networks with normal degree distribution.