Fast and Accurate Mining the Community Structure: Integrating Center Locating and Membership Optimization
Fast and Accurate Mining the Community Structure: Integrating Center Locating and Membership Optimization
复制标题
快速精准挖掘社区结构：集中心定位与会员优化于一体
DOI：
10.1109/tkde.2016.2563425
复制
发表时间：
2016-09-01
影响因子：
8.9
通讯作者：
Shi, Yong
中科院分区：
文献类型：
--
作者：
Li, Hui-Jia;Bu, Zhan;Shi, Yong
挖掘网络中的社区或集群在分析、设计和优化许多自然和工程复杂系统中是有价值的，例如，蛋白质网络、电网和运输系统。大多数现有技术将社区挖掘问题视为基于给定质量函数的优化问题（例如，模块化），但是它们都没有系统的理论来识别网络中的中心节点。此外，如何协调采矿效率和社区质量仍然是一个悬而未决的问题。在本文中，我们试图通过引入一种新的算法来解决上述挑战。首先，提出了一种具有可调影响因子的核函数来衡量每个节点的领导力，那些具有最高领导力的节点可以被视为候选中心节点。然后，我们使用一个离散时间动力系统来描述社区成员的动态分配，并制定了几个条件，以保证每个节点的动态轨迹收敛，通过它可以揭示网络的层次社区结构。该动力系统与所使用的质量函数无关，因此也可以应用于其他社区挖掘模型。我们的算法是非常高效的：计算复杂度分析表明，执行时间几乎是线性依赖于稀疏网络中的节点数量。最后，我们将该算法应用于一组合成基准网络和真实网络来验证算法的性能。
Mining communities or clusters in networks is valuable in analyzing, designing, and optimizing many natural and engineering complex systems, e.g., protein networks, power grid, and transportation systems. Most of the existing techniques view the community mining problem as an optimization problem based on a given quality function(e.g., modularity), however none of them are grounded with a systematic theory to identify the central nodes in the network. Moreover, how to reconcile the mining efficiency and the community quality still remains an open problem. In this paper, we attempt to address the above challenges by introducing a novel algorithm. First, a kernel function with a tunable influence factor is proposed to measure the leadership of each node, those nodes with highest local leadership can be viewed as the candidate central nodes. Then, we use a discrete-time dynamical system to describe the dynamical assignment of community membership; and formulate the serval conditions to guarantee the convergence of each node's dynamic trajectory, by which the hierarchical community structure of the network can be revealed. The proposed dynamical system is independent of the quality function used, so could also be applied in other community mining models. Our algorithm is highly efficient: the computational complexity analysis shows that the execution time is nearly linearly dependent on the number of nodes in sparse networks. We finally give demonstrative applications of the algorithm to a set of synthetic benchmark networks and also real-world networks to verify the algorithmic performance.