1. 吉林大学计算机科学与技术学院,吉林,长春,130012
2. 吉林大学符号计算与知识工程教育部重点实验室,吉林,长春,130012
纸质出版:2011
移动端阅览
金弟, 刘大有, 杨博, 等. 基于局部探测的快速复杂网络聚类算法[J]. 电子学报, 2011,39(11):2540-2546.
JIN Di, LIU Da-you, YANG Bo, et al. Fast Complex Network Clustering Algorithm Using Local Detection[J]. Acta Electronica Sinica, 2011, 39(11): 2540-2546.
目前复杂网络的规模越来越庞大
且呈现天然的分布式特性
因此从局部观点出发提出快速网络聚类算法就成为迫切需要.为解决这一问题
本文基于对网络模块性函数
Q
的分析
推导出一个针对于单个结点的局部目标函数
f
并证明
Q
函数随网络中任一结点的
f
函数呈单调递增趋势
进而提出一个基于局部优化的近线性网络聚类算法FNCA.在该算法中
每个结点仅利用网络的局部簇结构信息来优化自身的目标函数
f
所有结点通过相互协同来实现对整个网络的聚类.通过计算机生成网络和真实网络对算法FNCA进行测试
实验表明
该算法的运行效率和聚类质量都要明显优于当前的一些优秀网络聚类算法.
Recently
complex networks are always very huge and take on distributed nature.Therefore it is gradually becoming instant requirement to propose fast network clustering algorithms in the sight of local view.For the problem
this paper deduces a local objective function
f
aiming to each node in the network
which is based on the profound analysis on network modularity function
Q
and proves that
Q
is monotone increasing with function
f
of any node
and then proposes a fast network clustering algorithm (FNCA) by using local optimization.In this algorithm
each node optimizes its own objective function
f
by only local information
and all the nodes collectively optimize function
Q
to detect network community structure.Both efficiency and ef
fectiveness of algorithm FNCA are tested against computer-generated and real-world networks.Experimental result shows that this algorithm is better than some excellent network clustering algorithms in term of these two respects.
0
浏览量
1570
下载量
15
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621