论文标题
通过特征值高程断开图的边缘增强
Edge Augmentation on Disconnected Graphs via Eigenvalue Elevation
论文作者
论文摘要
提出了基于分离的子图内的社区内连接性，确定最有可能的社区间边缘的图理论任务。基于提高图形频谱的零特征值，为此边缘增强任务开发了一种算法。特征值高程振幅和相应增强边缘密度的上限被得出，并在随机图上通过模拟进行身份验证。该算法在合成和真实网络之间始终如一地工作，在连接图组件下产生了理想的性能。在不同的社区检测方法（Girvan-Newman方法，贪婪的模块化最大化，标签传播，Louvain方法和流体群落）下，边缘增强反向工程分区，在大多数情况下，以> 50％的频率产生社区间边缘。
The graph-theoretical task of determining most likely inter-community edges based on disconnected subgraphs' intra-community connectivity is proposed. An algorithm is developed for this edge augmentation task, based on elevating the zero eigenvalues of graph's spectrum. Upper bounds for eigenvalue elevation amplitude and for the corresponding augmented edge density are derived and are authenticated with simulation on random graphs. The algorithm works consistently across synthetic and real networks, yielding desirable performance at connecting graph components. Edge augmentation reverse-engineers graph partition under different community detection methods (Girvan-Newman method, greedy modularity maximization, label propagation, Louvain method, and fluid community), in most cases producing inter-community edges at >50% frequency.
