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

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.

     

/

返回文章
返回