Defining and identifying cograph communities in complex networks
Defining and identifying cograph communities in complex networks
复制标题
定义和识别复杂网络中的图谱社区
DOI：
10.1088/1367-2630/17/1/013044
复制
发表时间：
2015-01-20
影响因子：
3.3
通讯作者：
Wang, Haiyang
中科院分区：
文献类型：
--
作者：
Jia, Songwei;Gao, Lin;Wang, Haiyang
社区或模块检测是复杂网络中的一个基本问题。现有的传统算法大多只关注子图中节点之间的稠密连接，而与子图外节点的松散连接，忽略了社区的拓扑结构。然而，在大多数情况下，人们需要对社区的内部拓扑结构进行进一步的分析，以获得各种有意义的子群。因此，我们提出了一个新的社区被称为cograph社区，它有一个很好的理解结构。上图及其对应的上树表示的良好理解的结构允许立即识别结构等价的子群。我们开发了一种算法称为边缘P4中心为基础的分裂算法（EPCA）来检测这些cograph社区，该算法是有效的，无参数和独立的额外措施，主要是由于新的本地边缘P4中心性措施。此外，我们比较了EPCA与现有文献中合成，社会和生物网络的算法，以显示它具有上级或竞争力的准确性。除了计算上的优势，其他社区检测算法，EPCA提供了一个简单的方法，发现密集和稀疏的子组的基础上结构等价或同质的角色，否则可能会被其他算法，依赖于边缘密度的措施，寻找子群未被检测到。
Community or module detection is a fundamental problem in complex networks. Most of the traditional algorithms available focus only on vertices in a subgraph that are densely connected among themselves while being loosely connected to the vertices outside the subgraph, ignoring the topological structure of the community. However, in most cases one needs to make further analysis on the interior topological structure of communities to obtain various meaningful subgroups. We thus propose a novel community referred to as a cograph community, which has a well-understood structure. The well-understood structure of cographs and their corresponding cotree representation allows for an immediate identification of structurally-equivalent subgroups. We develop an algorithm called the Edge P4 centrality-based divisive algorithm (EPCA) to detect these cograph communities; this algorithm is efficient, free of parameters and independent of additional measures mainly due to the novel local edge P4 centrality measure. Further, we compare the EPCA with algorithms from the existing literature on synthetic, social and biological networks to show it has superior or competitive performance in accuracy. In addition to the computational advantages over other community-detection algorithms, the EPCA provides a simple means of discovering both dense and sparse subgroups based on structural equivalence or homogeneous roles which may otherwise go undetected by other algorithms which rely on edge density measures for finding subgroups.