一种新型简单图社区结构发现算法

doi:10.3778/j.issn.1002-8331.2009.25.045

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (25): 148-150.DOI: 10.3778/j.issn.1002-8331.2009.25.045

一种新型简单图社区结构发现算法

胡健¹，邓志娟¹，杨炳儒²

1.江西理工大学信息工程学院，江西赣州 341000
2.北京科技大学信息工程学院，北京 100083

收稿日期:2008-05-14 修回日期:2008-07-28 出版日期:2009-09-01 发布日期:2009-09-01
通讯作者: 胡健

New community structure discovery algorithm of simple graph

HU Jian¹，DENG Zhi-juan¹，YANG Bing-ru²

1.School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou，Jiangxi 341000，China
2.School of Information Engineering，University of Science and Technology Beijing，Beijing 100083，China

Received:2008-05-14 Revised:2008-07-28 Online:2009-09-01 Published:2009-09-01
Contact: HU Jian

摘要/Abstract

摘要： 在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边凝聚系数的概念，提出了基于边凝聚系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。

关键词: 社区结构, 社区发现, 边凝聚系数

Abstract: The automatic search and community discovery in large and complex network has important practical applications.The hypergraph based model and cluster algorithm in community structure discovery is applied.This paper introduces the concept of Edge Clustering Coefficient（ECC） to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC.Enron e-mail data sets will be test data sets.Through comparative analysis of algorithm，it is proved that this algorithm can significantly improve the time complexity.

Key words: community structure, community discovery, edge clustering coefficient

中图分类号:

TP301.6

胡健¹，邓志娟¹，杨炳儒². 一种新型简单图社区结构发现算法[J]. 计算机工程与应用, 2009, 45(25): 148-150.

HU Jian¹，DENG Zhi-juan¹，YANG Bing-ru². New community structure discovery algorithm of simple graph[J]. Computer Engineering and Applications, 2009, 45(25): 148-150.

[1]	刘家骥，包崇明，周丽华，王崇云，孔兵. 图正则化非负矩阵分解的异质网社区发现[J]. 计算机工程与应用, 2020, 56(21): 131-138.
[2]	于千城，於志文，王柱. 对抗样本训练图分类器进行模型推理质量评估[J]. 计算机工程与应用, 2020, 56(17): 142-149.
[3]	张晓琴，刘莉楠. 基于亲密度和吸引力的二分网络社区发现算法[J]. 计算机工程与应用, 2019, 55(23): 170-176.
[4]	王斌，李强，盛津芳，孙泽军. 基于边图的线性流重叠社区发现算法[J]. 计算机工程与应用, 2019, 55(2): 60-66.
[5]	廖宇1，朱福喜1，2，刘世超1. 基于Skip-gram模型的社区查询算法[J]. 计算机工程与应用, 2018, 54(8): 143-148.
[6]	林定1，2，徐颖1，2，黄国新1，2，陈崇成1，2. 基于Louvain算法的图数据三维树形可视化[J]. 计算机工程与应用, 2018, 54(7): 96-101.
[7]	孙成成，席景科，占文威，李懂. 基于最大团的层次化重叠社区发现算法[J]. 计算机工程与应用, 2018, 54(18): 105-109.
[8]	李辉，降爱莲. 可探测社区稳定结构的局部社区发现算法[J]. 计算机工程与应用, 2017, 53(23): 54-59.
[9]	陈晓1，2，3，郭景峰1，3，范超智1，3. 基于联系度的主题关注网络社区发现方法研究[J]. 计算机工程与应用, 2017, 53(17): 85-93.
[10]	赵卫绩1，2，张凤斌2，刘井莲1，金昊1. 一种基于中心极大团扩展的社区挖掘算法[J]. 计算机工程与应用, 2017, 53(15): 164-169.
[11]	刘立寒1，方志祥1，萧世伦2，尹凌3. 带源节点的快速社区发现算法[J]. 计算机工程与应用, 2016, 52(23): 75-80.
[12]	康茜1，李德玉1，2，王素格1，2，冀庆斌1. 传播过程中信号缺失的层次聚类社区发现算法[J]. 计算机工程与应用, 2015, 51(9): 201-206.
[13]	张鑫，刘秉权，王晓龙. 复杂网络中社区发现方法的研究[J]. 计算机工程与应用, 2015, 51(24): 1-7.
[14]	方平1，3，4，李芝棠2，3，4，涂浩2，4，郭正彪3，4. 复杂网络局部社区挖掘的节点接近度算法[J]. 计算机工程与应用, 2013, 49(17): 38-42.
[15]	李瑾1，周竹荣2. 基于用户行为和社区发现的P2P资源检索方法[J]. 计算机工程与应用, 2012, 48(21): 94-98.

一种新型简单图社区结构发现算法

New community structure discovery algorithm of simple graph

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics