Community Detection in Scale-Free Networks using Edge Weight and Modularity Optimization Method

• Jarukasemratana Sorn

  Tokyo Institute of Technology

• Murata Tsuyoshi

  Tokyo Institute of Technology

抄録

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 scale-free 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 scale-free 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.

収録刊行物

• 人工知能学会論文誌

  人工知能学会論文誌 30 (1), 84-95, 2015

  一般社団法人 人工知能学会

キーワード

• community detection
• scale-free network
• edge weight
• modularity

詳細情報

• CRID: 1390282680084742400
• NII論文ID: 130004927376
• DOI: 10.1527/tjsai.30.84
• ISSN: 13468030
• ISSN: 13460714
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可