万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ( 信息科学版), 2019, 44(10): 1545-1552. DOI: 10.13203/j.whugis20180025
引用本文: 万幼, 刘耀林. 基于地理加权中心节点距离的网络社区发现算法[J]. 武汉大学学报 ( 信息科学版), 2019, 44(10): 1545-1552. DOI: 10.13203/j.whugis20180025
WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. DOI: 10.13203/j.whugis20180025
Citation: WAN You, LIU Yaolin. Community Detection Algorithm Based on Geographical Weighted Central Node Distance[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1545-1552. DOI: 10.13203/j.whugis20180025

基于地理加权中心节点距离的网络社区发现算法

Community Detection Algorithm Based on Geographical Weighted Central Node Distance

  • 摘要: 提出一种基于地理加权中心节点距离的网络社区发现算法(geographical weighted central node distance based Louvain method,GND-Louvain)。该算法扩展了传统复杂网络领域的经典社区发现方法Louvain,利用地理加权中心节点来度量社区发现过程中的空间距离关系,并将此距离衰减效应加入到距离模块度模型中,以此来计算和评估空间网络社区划分结果的质量,并探究了空间社区发现结果不稳定的原因。通过定义节点计算顺序,保证了社区发现结果的质量和稳定性。利用中国铁路网线路数据,设计了5种不同空间约束的空间社区发现对比性实验。结果证明,GND-Louvain算法的准确性最高,并且算法结果最稳定。

     

    Abstract: Community detection is an important topic in spatial network researches. It can discover interesting spatial patterns, which help understand the spatial structures hidden in the networks. However, community detection in spatial networks is more difficult than traditional networks. Since it has to consider some other spatial correlations, e.g., spatial contiguity, geographic distance. This paper proposes a new spatial community detection algorithm-geographial weighted central node distance based Louvain method (GND-Louvain). It uses a geographical and network dual-constrain to measure the distance and to calculate the distances decay effects between spatial nodes and meta-communities. It also extends the famous fast unfolding community detection algorithm-Louvain, by using the distance-modularity. In addition, a merge order is defined during the GND-Louvain's optimization process to get high quality and stable community results. Comparative experiments are designed on five different community detection methods based on five different spatial constraints, which are ① no distance constraint, ② spatial contiguity edge constraint, ③ geometry median center distance, ④ degree center distance, and ⑤ degree weighted geometry median center distance. The experimental data comes from the Chinese railway lines. And results prove that the newly defined GND-Louvain algorithm can produce more accurate spatial communities than others. And the merge orders also ensure the high quality and stable results.

     

/

返回文章
返回