论文标题
网络社区检测和聚类与随机步行
Network community detection and clustering with random walks
论文作者
论文摘要
我们提出了一种将网络节点划分为非重叠社区的新方法，这是揭示网络模块化和分层组织的关键步骤。我们的方法适用于具有加权和未加权对称边缘的网络，使用随机步行来探索同一社区的相邻节点。步行型算法（WLA）可将网络节点的最佳分区分为给定的社区。步行类型社区发现者（WLCF）采用WLA来预测最佳的社区和相应的网络分区。我们已经对这两种算法进行了广泛的基准测试，发现它们在预测分区的模块化和社区之间的链接数方面均优于其他方法或匹配其他方法。利用我们方法的计算效率，我们研究了科罗拉多州道路和交叉路口的大规模图。我们的聚类在邻近社区之间产生了地理上明智的界限。
We present a novel approach to partitioning network nodes into non-overlapping communities - a key step in revealing network modularity and hierarchical organization. Our methodology, applicable to networks with both weighted and unweighted symmetric edges, uses random walks to explore neighboring nodes in the same community. The walk-likelihood algorithm (WLA) produces an optimal partition of network nodes into a given number of communities. The walk-likelihood community finder (WLCF) employs WLA to predict both the optimal number of communities and the corresponding network partition. We have extensively benchmarked both algorithms, finding that they outperform or match other methods in terms of the modularity of predicted partitions and the number of links between communities. Making use of the computational efficiency of our approach, we investigated a large-scale map of roads and intersections in the state of Colorado. Our clustering yielded geographically sensible boundaries between neighboring communities.
