基于虚拟力牵引的社团划分算法

文中基于虚拟引力的思想,提出了一种新的社团划分算法.其基本思想是将相连节点之间看作是引力,不相连节点看作是斥力,让节点之间进行相互作用,直到节点以社团的形式聚集起来,从而达到划分社团的目的.通过在计算机生成网络和已知社团结构的现实网络中对本算法进行仿真,发现算法具有较高可靠性和接近线性的时间复杂度.

Community Partitioning Algorithm Based on Virtual Force

Investigating the inner community structure is supposed to be one of the best approaches to study an unknown complex network.Based on the object oriented methodology,here we propose a novel community partitioning algorithm,in which the relation between the adjacent vertices is considered as attraction while the relation between the non-adjacent vertices is repulsion.The community structure is formed by the self-organization of vertices which are influenced by the virtual force of their neighbors.This algorithm is based on a new network structure and its operation efficiency is significantly improved.The reliability of this algorithm is tested by applying it in a computer-generated network and a real-world network with known structure.Finally,an improvement of the algorithm is also discussed,with the purpose to enhance the efficiency and accuracy of the algorithm.