基于集聚系数的链接社区发现方法

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (4): 449–456.

基于集聚系数的链接社区发现方法

王志超;于剑;柴变芳;

出版日期:2013-08-30 发布日期:2013-08-30
作者简介:北京交通大学计算机与信息技术学院;石家庄经济学院信息工程系;
基金资助:
基金:北京市自然科学基金项目面上基金(4112046)

L i n kc o mm u n i t i e sd e t e c t i o no nc l u s t e r i n gc o e f f i c i e n t

W a n gZ h i - C h a o 1 , Y uJ i a n 1* * , C h a iB i a n - F a n g 1, 2

Online:2013-08-30 Published:2013-08-30
About author:( 1. S c h o o l o fC o m p u t e ra n dI n f o r m a t i o nT e c h n o l o g y , B e i j i n gJ i a o t o n gU n i v e r s i t y , B e i j i n g , 1 0 0 0 4 4 , C h i n a ;
2. D e p a r t m e n to f I n f o r m a t i o nE n g i n e e r i n g , S h i j i a z h u a n gU n i v e r s i t yo fE c o n o m i c s , S h i j i a z h u a n g , 0 5 0 0 3 1 , C h i n a )

摘要/Abstract

摘要： 提出一种基于节点集聚系数的链接社区发现方法LCDCC(link communities detection on clustering coefficient),该方法假设社区是网络中的稠密子图,利用网路节点的集聚系数及重叠度发现链接社区.LCDCC可更直观地识别重叠社区;与基于相似度矩阵的聚类方法、统计推理等方法相比,LCDCC可精确地在网络规模的线性时间内发现高浓度链接社区,同时可识别多种角色的节点,如重叠点、桥节点、叶子点等.在人工网络和真实网络上的实验表明,LCDCC可以快速有效的发现有意义的重叠社区结构.

Abstract: W ep r o p o s e dam e t h o d , n a m e dL C D C C , f o r l i n kc o mm u n i t i e sd e t e c t i o no nc l u s t e r i n gc o e f f i c i e n t . B a s e do n
t h ea s s u m p t i o nt h a t c o mm u n i t y i s ad e n s e s u b g r a p h i nt h en e t w o r k , L C D C Cu s e s t h e c l u s t e r i n gc o e f f i c i e n t a n do v e r -
l a p p i n gd e g r e eo f e a c hv e r t e x i nt h en e t w o r kt od e t e c t l i n kc o mm u n i t i e s , w h i c hm a k e s i tm o r e i n t u i t i v et or e c o g n i z e
o v e r l a p p i n gc o mm u n i t i e s . C o m p a r e dw i t h t h em e t h o d sb a s e do ns i m i l a r i t ym a t r i xa n d t h em e t h o d sb a s e do ns t a t i s t i c s
i n f e r e n c e , L C D C Cc a nd e t e c td e n s el i n kc o mm u n i t i e si nl i n e a rt i m ec o m p l e x i t y m o r ep r e c i s e l y . I na d d i t i o n , i tc a n
r e c o g n i z et h ev e r t i c e s w i t hd i f f e r e n tk i n d so fr o l e s , s u c ha so v e r l a p p i n gv e r t i c e s , b r i d g ev e r t i c e s , a n do u t l i e r s .
E x p e r i m e n t a l r e s u l t so nr e a l - w o r l da n ds y n t h e t i cn e t w o r k ss h o wt h a tL C D C Cc a nf i n dm e a n i n g f u l o v e r l a p p i n gc o m -
m u n i t i e sq u i c k l ya n de f f i c i e n t l y .

王志超;于剑;柴变芳;. 基于集聚系数的链接社区发现方法[J]. 南京大学学报(自然科学版), 2013, 49(4): 449–456.

W a n gZ h i - C h a o 1 , Y uJ i a n 1* * , C h a iB i a n - F a n g 1, 2. L i n kc o mm u n i t i e sd e t e c t i o no nc l u s t e r i n gc o e f f i c i e n t[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(4): 449–456.

参考文献

[ 1 ] W a t t sDJ , S t r o g a t zS H. C o l l e c t i v ed y n a m i c so f “ s m a l l - w o r l d ” n e t w o r k s .N a t u r e , 1 9 9 8 , 3 9 3 : 4 4 0~4 4 2.
[ 2 ] B a r a b á s iA L , B o n a b e a uE. S c a l e - f r e en e t w o r k s . S c i e n t i f i cAm e r i c a n , 2 0 0 3 , M a y : 5 0~5 9.
[ 3 ] G i r v a nM , N e wm a nM EJ . C o mm u n i t ys t r u c t u r e i ns o c i a la n db i o l o g i c a ln e t w o r k s . P r o c e e d i n g so f t h eN a t i o n a lA c a d e m yo fS c i e n c e so ft h eU n i t e d S t a t e so fAm e r i c a , 2 0 0 2 , 9 9 ( 1 2 ) : 7 8 2 1~7 8 2 6.
[ 4 ] N e wm a n M EJ . F a s t A l g o r i t h m f o rd e t e c t i n g c o mm u n i t y s t r u c t u r e i n n e t w o r k s .P h y s i c a lR e v i e wE , 2 0 0 4 , 6 9 ( 6 ) : 0 6 6 1 3 3.
[ 5 ] C a p o c c iA , S e r v e d i oV D P , C a l d a r e l l iG , e ta l . D e t e c t i n g c o mm u n i t i e s i n l a r g e N e t w o r k s . P h y s i c a A : S t a t i s t i c a l M e c h a n i c s a n d I t s A p p l i c a t i o n s , 2 0 0 5 , 3 5 2 ( 2-4 ) : 6 6 9~6 7 6.
[ 6 ] R o s v a l l M , B e r g s t r o m C T.M a p s o fr a n d o m w a l k so nc o m p l e x n e t w o r k sr e v e a lc o mm u n i t y t r u c t u r e . P r o c e e d i n g so ft h eN a t i o n a lA c a d e m y o fS c i e n c e so ft h e U n i t e d S t a t e so f Am e r i c a ,
2 0 0 8 , 1 0 5 ( 4 ) : 1 1 1 8~1 1 2 3.
[ 7 ] R a g h a v a nU N , A l b e r tR , K u m a r aS. N e a r l i n e a r t i m ea l g o r i t h mt od e t e c t c o mm u n i t ys t r u c t u r e s i n
l a r g e - s c a l en e t w o r k s . P h y s i c a lR e v i e wE , 2 0 0 7 , 7 6 ( 3 ) : 0 3 6 1 0 6.
[ 8 ] C h e nJ , Y o u s e f S . D e n s e s u b g r a p he x t r a c t i o nw i t h a p p l i c a t i o n t o c o mm u n i t y d e t e c t i o n .I E E E T r a n s a c t i o n s o n K n o w l e d g e a n d D a t a E n g i n e e r i n g . 2 0 1 2 , 2 4 ( 7 ) : 1 2 1 6~1 2 3 0.
[ 9 ] P a l l aG , D e r e n y i I , F a r k a s I , e t a l . U n c o v e r i n gt h eo v e r l a p p i n g c o mm u n i t y s t r u c t u r e o f c o m p l e x n e t w o r k s i nn a t u r ea n ds o c i e t y . N a t u r e , 2 0 0 5 , 4 3 5 ( 7 0 4 3 ) : 8 1 4~8 1 8.
[ 1 0 ] Z h a n g S , W a n g R , Z h a n g X. I d e n t i f i c a t i o n o f o v e r l a p p i n g c o mm u n i t y s t r u c t u r e i n c o m p l e x n e t w o r k su s i n g f u z z yC - m e a n s c l u s t e r i n g . P h y s i c a S t a t i s t i c a l M e c h a n i c sa n di t s A p p l i c a t i o n s ,
2 0 0 7 , 3 7 4 ( 1 ) : 4 8 3~4 9 0.
[ 1 1 ] Z h a n gS , W a n gRS , Z h a n gXS . U n c o v e r i n g f u z z y c o mm u n i t y s t r u c t u r e i n c o m p l e x n e t w o r k s . P h y s i c a lR e v i e wE , 2 0 0 7 , 7 6 ( 4 ) : 0 4 6 1 0 3.
[ 1 2 ] N e wm a nM E , L e i c h tE A. M i x t u r e M o d e l sa n d e x p l o r a t o r ya n a l y s i si nn e t w o r k s . P r o c e e d i n g so ft h eN a t i o n a lA c a d e m yo fS c i e n c e so ft h eU n i t e d S t a t e so fAm e r i c a , 2 0 0 7 , 1 0 4 ( 2 3 ) : 9 5 6 4~9 5 6 9.
[1 3 ] A h n Y Y , B a g r o w J P , L e h m a n n S.L i n kc o mm u n i t i e s r e v e a l m u l t i s c a l e c o m p l e x i t y i n n e t w o r k s . N a t u r e , 2 0 1 0 , 4 6 6 : 7 6 1~7 6 4.
[1 4 ] B r i a nB , B r i a nK , N e w m a n M EJ . A ne f f i c i e n ta n d p r i n c i p l e d m e t h o d f o r d e t e c t i n g c o mm u n i t i e s i n n e t w o r k s . P h y s i c a lR e v i e wE2 0 1 1 , 8 4 : 0 3 6 1 0 3 .
[ 1 5 ] E v a n s T , L a m b i o t t e R.L i n e g r a p h s , l i n kp a r t i t i o n s , a n do v e r l a p p i n gc o mm u n i t i e s . P h y s i c a l R e v i e wE , 2 0 0 9 , 8 0 ( 1 ) : 1 6 1 0 5.
[ 1 6 ] C h e n gX Q , S h e n H W. C o mm u n i t ya n a l y s i si ns o c i a li n f o r m a t i o n n e t w o r k s .C h i n a C o m p u t e r F e d e r a t i o n , 2 0 1 1 , 7 ( 1 2 ) : 1 2~1 9. ( 程学旗, 沈华伟 . 社会信息网络中的社区分析 . 中国计算机学会通讯,2 0 1 1 , 7 ( 1 2 ) : 1 2~1 9.
[ 1 7 ] N e w m a n M E J . T h es t r u c t u r ea n df u n c t i o n o f c o m p l e xn e t w o r k s . S o c i e t yf o r I n d u s t r ya n dA p p l i e dM a t h e m a t i c sR e v i e w , 2 0 0 3 , 4 5 : 1 6 7 ~ 2 5 6 .
[ 1 8 ] W a t t sD J , S t r o g a t zS H. C o l l e c t i v ed y n a m i c so f ‘ s m a l l - w o r l d ’ n e t w o r k s . N a t u r e , 1 9 9 8 , 3 9 3 : 4 4 0 ~ 4 4 2 .
[ 1 9 ] Z a c h a r y W W. A ni n f o r m a t i o nf l o w m o d e lf o rc o n f l i c ta n df i s s i o ni ns m a l lg r o u p s . J o u r n a lo f A n t h r o p o l o g i c a lR e s e a r c h , 1 9 7 7 , 3 3 : 4 5 2~4 7 3.
[ 2 0 ] K n u t hDE. T h eS t a n f o r dG r a p h B a s e : Ap l a t f o r mf o r c o m b i n a t o r i a lc o m p u t i n g .A d d i s o n - W e s l e y ,R e a d i n g , M a s s a c h u s e t t s ,1 9 9 3.
[ 2 1 ] S e nP , N a m a t eG M , B i l g i c M , e ta l . C o l l e c t i v e c l a s s i f i c a t i o n i n n e t w o r k d a t a .A I M a g a z i n e , 2 0 0 8 , 2 9 ( 3 ) : 9 3~1 0 6.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed