一种解决网络社区划分物理算法  

A Physical Community Discovery Algorithm

作　　者：王存睿[1,2] 段晓东[1] 刘向东[1] 李志洁[1] 

机构地区：[1]大连民族学院非线性信息技术研究所,辽宁大连116600 [2]东北大学研究生院,辽宁沈阳110004

出　　处：《微电子学与计算机》2010年第9期33-36,共4页Microelectronics & Computer

基　　金：国家自然科学基金项目(60573124);辽宁省自然科学基金(20072197);高校科研计划项目(20060146)

摘　　要：网络结构挖掘目前是非规则数据的数据挖掘技术研究的热点之一,其中网络结构划分在并行计算和互联网结构分析中具有重要的实用价值.将电荷互斥和弹簧胡克定律引入网络结构划分,用其构建了网络中节点间的各种作用力,使得网络在力作用下产生相应运动,然后,在各种力的作用下达到平衡状态,将此平衡状态映射到二维平面,再将原先网络中的节点当作平面中的数据样本点.这样可以将网络结构信息(n+m)(其中n为网络中的节点个数,m为网络边的个数)压缩到2n,然后通过聚类算法对其进行划分.构建此算法并用多种算法与传统的GN分裂算法进行对比,发现新算法的划分质量与高效的GN算法相当,新算法还可以通过节点代表对网络进行约减,使得算法的速度可以根据精度调节.本算法的构建为网络结构划分提供了一种新的途径,同时对网络平衡状态的研究提出了相应的方法.Community detection algorithm is very important to parallel computing and Internet structure analysis. This paper designs a new algorithm for Community Discovery based on building the various forces in network making the network movie randomly by Hooke＇ s Law and Coulomb＇ s Law, then reach a balance by a variety of forces, this balance is used to map network to two-dimensional vector. And then the nodes of original network become the data points in 2d plane. This way can compress （ n ＋ m） network structure information down to 2n （Here n is the number of nodes in the network, m is the number of edges in the network）, and then make duster algorithm to carry out the division of these 2d data points. In this paper, the algorithm is compared with the traditional GN algorithm, the experiment indicates that new algorithm can match the efficient GN algorithm, and can get more efficient and accurate by selecting some sample of data points in the plane. The algorithm provides a new way to partition network and takes a new way to study the balance of network.

关 键 词：复杂网络 结构挖掘 结构划分 

分 类 号：N945[自然科学总论—系统科学]