New community structure discovery algorithm of simple graph

doi:10.3778/j.issn.1002-8331.2009.25.045

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (25): 148-150.DOI: 10.3778/j.issn.1002-8331.2009.25.045

• 数据库、信息处理 • Previous Articles Next Articles

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

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

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

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

通讯作者: 胡健

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

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

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

CLC Number:

TP301.6

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.

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

[1]	WANG Bin, LI Qiang, SHENG Jinfang, SUN Zejun. Linear Streaming Algorithm for Overlapping Community Detection Based on Link Graph [J]. Computer Engineering and Applications, 2019, 55(2): 60-66.
[2]	LIN Ding1, 2, XU Ying1, 2, HUANG Guoxin1, 2, CHEN Chongcheng1, 2. Visualizing graph data in 3D tree-style based on Louvain algorithm [J]. Computer Engineering and Applications, 2018, 54(7): 96-101.
[3]	DU Wenju1, ZHANG Jiangang2, YU Jianning1. Research on stability?of complex bus community network model [J]. Computer Engineering and Applications, 2017, 53(23): 39-46.
[4]	ZHAO Weiji1，2, ZHANG Fengbin2, LIU Jinglian1, JIN Hao1. Community mining algorithm based on central maximal-clique expansion [J]. Computer Engineering and Applications, 2017, 53(15): 164-169.
[5]	YANG Qiang, LU Gang. Establishment and study of properties of Weibo social network model [J]. Computer Engineering and Applications, 2016, 52(12): 42-48.
[6]	MIN Liang1, SHAO Liangshan2, ZHAO Yonggang1. Community detection based on node similarity [J]. Computer Engineering and Applications, 2015, 51(9): 77-81.
[7]	XIAO Zihong. Research on difference equation in community-finding of complex network [J]. Computer Engineering and Applications, 2012, 48(25): 149-153.
[8]	LAN Mingming, HAN Hua, LIU Wanlu. Study on invulnerability measure based on community structure of complex networks [J]. Computer Engineering and Applications, 2012, 48(23): 67-71.
[9]	LI Jin1, ZHOU Zhurong2. Search method of P2P resource based on user behavior and community discovery [J]. Computer Engineering and Applications, 2012, 48(21): 94-98.
[10]	KONG Jian1，XIE Fuding1，SUN Yan1，ZHAO Fengxia2. Classification method in complex networks based on Semi-supervising [J]. Computer Engineering and Applications, 2011, 47(4): 47-49.
[11]	DING Dewu1，WU Pu1，2，JI Bojing1，2，WANG Ruchuan2. Research on community structure in metabolic network based on link clustering [J]. Computer Engineering and Applications, 2011, 47(34): 141-144.
[12]	REN Junliang1，SHEN Maoxing1，TONG Rui1，GAO Hongxing2. Study of reducing size of cascading failures in scale-free network [J]. Computer Engineering and Applications, 2011, 47(33): 82-84.
[13]	SHI Yuzhen1，2，PENG Zhiyong3. Research on experts community discovery based on modified h index [J]. Computer Engineering and Applications, 2011, 47(29): 1-3.
[14]	HUANG Hao-ying，MA Ying-hong. Detecting community algorithm based on signal process and hierarchical clustering [J]. Computer Engineering and Applications, 2010, 46(9): 51-54.
[15]	FU Li-dong^1，2. Kernel approach for detecting communities in complex networks based on semi-supervised clustering [J]. Computer Engineering and Applications, 2010, 46(5): 1-3.

New community structure discovery algorithm of simple graph

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics