论文标题
使用拓扑数据分析在大规模动态网络中有效的社区检测
Efficient Community Detection in Large-Scale Dynamic Networks Using Topological Data Analysis
论文作者
论文摘要
在本文中，我们提出了一种扩展基于持久性拓扑数据分析（TDA）的方法，该方法通常用于将形状表征为通用网络。我们介绍了社区树的概念，这是一种基于集团渗透方法的集团社区建立的树结构，以从持久的角度从网络中总结了拓扑结构。此外，我们通过维护跨越森林的形式的一系列集团图来开发有效的算法来构建和更新社区树，其中每个跨越的树都建在基础的欧拉旅游树上。通过社区树揭示的信息和相应的持久图，我们提出的方法能够检测集团社区，并在稳定性阈值的情况下跟踪其演变过程中的主要结构变化。结果证明了其在为时变社交网络提取有用的结构见解方面的有效性。
In this paper, we propose a method that extends the persistence-based topological data analysis (TDA) that is typically used for characterizing shapes to general networks. We introduce the concept of the community tree, a tree structure established based on clique communities from the clique percolation method, to summarize the topological structures in a network from a persistence perspective. Furthermore, we develop efficient algorithms to construct and update community trees by maintaining a series of clique graphs in the form of spanning forests, in which each spanning tree is built on an underlying Euler Tour tree. With the information revealed by community trees and the corresponding persistence diagrams, our proposed approach is able to detect clique communities and keep track of the major structural changes during their evolution given a stability threshold. The results demonstrate its effectiveness in extracting useful structural insights for time-varying social networks.
