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

Abstract

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.

Journal

• Transactions of the Japanese Society for Artificial Intelligence

  Transactions of the Japanese Society for Artificial Intelligence 30 (1), 84-95, 2015

  The Japanese Society for Artificial Intelligence

Keywords

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

Details

• CRID: 1390282680084742400
• NII Article ID: 130004927376
• DOI: 10.1527/tjsai.30.84
• ISSN: 13468030
• ISSN: 13460714
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed