基于有向拓扑势的用户角色分析方法

doi:10.3969/j.issn.1000-436x.2014.12.015

摘要/Abstract

摘要：

真实世界中存在大量有向、加权、动态的网络。针对有向加权网络的节点角色分析问题，提出了一种基于有向拓扑势的节点角色分析方法，该方法根据节点的行为模式及局部影响力将节点划分成4种角色。然后介绍了基于节点角色的动态网络演化分析方法，它能对角色行为进行动力学建模，展示了随时间连接模式的变化，并能检测较大影响的事件。实验结果表明，本方法能有效估计节点角色并检测动态网络的演化。

关键词: 社会化网络, 有向拓扑势, 角色分析, 动态网络演化

Abstract:

The majority of real-world networks are directed,weighted and dynamic.Aiming at the problem of node role analysis in directed weighted network,a novel node role analysis method based on directed topological potential is pro-posed,which can divide nodes into four roles based on their behavior pattern and local influence.Then,a node role-based dynamic networks evolution analysis method is introduced,which can model the dynamics of behavioral roles represent-ing the main connectivity patterns over time and detect the significant event.The experiment results indicate that pro-posed approaches can effectively estimate the node role and detect the dynamics of network evolution.

Key words: social network, directed topological potential, role analysis, dynamics of network evolution

段松青,于兴隆,吴斌,王柏. 基于有向拓扑势的用户角色分析方法[J]. 通信学报, 2014, 35(12): 124-135.

Song-qing DUAN,Xing-long YU,Bin WU,Bai WANG. User role analysis method based on directed topological potential[J]. Journal on Communications, 2014, 35(12): 124-135.

图/表 19

图1

图2

图3

图4

图5

表1

表2

图6

表3

图7

表4

表5

表6

图8

图9

图10

图11

图12

图13

参考文献 16

[1]	FREEMAN L C . The development of social network analysis:A study in the sociology of science[M]. Vancouver: Empirical Press, 2004.
[2]	ZHU T , WANG B , WU B . Role defining using behavior-based clus-tering in telecommunication network[J]. Expert Systems with Applica-tions, 2011,38(4):3902-3908.
[3]	LI B X , LI M J . A brief review of applications of social network analysis against terrorism[J]. Complex Systems and Complexity Sci-ence, 2012,9(2):85-93.
[4]	SCOTT J . Social Network Analysis:A Handbook[M]. California:SAGE Publications, 1991.
[5]	LORRAIN F , WHITE H . Structural equivalence of individuals in social networks[J]. Journal of Mathematical Socioology, 1971,1(1):49-80.
[6]	GUIMERA R , SALES-PARDO M , AMARAL L A N . Classes of com-plex networks defined by role-to-role connectivity profiles[J]. Nature Physics, 2007,3(63):69-80.
[7]	HU J , HAN Y N , HU J . Topological potential:modeling node impor-tance with activity and local effect in complex networks[A]. Computer Modeling and Simulation,Second International Conference[C]. 2010.411-415.
[8]	HE N , GAN W Y , LI D Y . Evaluate nodes importance in the network using data field theory[A]. International Conference on Convergence Information Technology[C]. 2007.1225-1230.
[9]	肖俐平，孟晖，李德毅 . 基于拓扑势的网络节点重要性排序及评价方法[J]. 武汉大学学报(信息科学版), 2008,33(4):379-383. XIAO L P , MENG H , LI D Y . Approach to node ranking in a network based on topology potential[J]. Geometrics and Information Science of Wuhao University, 2008,33(4):379-383.
[10]	淦文燕，赫南，李德毅等. 一种基于拓扑势的网络社区发现方法[J]. 软件学报， 2009,20(8):2241-2254. GAN W Y , HE N , LI D Y ,et al. Community discorery method in net-works based on topology poetical[J]. Journal of Software, 2009,20(8):2241-2254.
[11]	张健沛，李泓波，杨静等. 基于拓扑势的网络社区结点重要度排序算法[J]. 哈尔滨工程大学学报， 2012,33(6):745-752. ZHANG J P , LI H B , YANG J ,et al. An importance-sorting algorithm of network community nodes based on topological potential[J]. Jour-nal of Harbin Engineering University, 2012,33(6):745-752.
[12]	张健沛，李泓波，杨静等. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报， 2012,40(12):2512-2518. ZHANG J P , LI H B , YNAG J ,et al. Variable scale network overlap-ping community identification based on identity uncertainty[J]. Acta Electronica Sinica, 2012,40(12):2512-2518.
[13]	李泓波，张健沛，杨静等. 基于社区节点重要性的社会网络压缩方法[J]. 北京大学学报 (自然科学版), 2013,49(1):117-125. LI H B , ZHANG J P , YANG J ,et al. Social network compression based on the importance of the community nodes[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2013,49(1):117-125.
[14]	赵东杰，王华，李德毅等. 基于拓扑势熵的维基百科词条编辑演化研究[J]. 科技导报， 2012,30(4):71-74. ZHAO D J , WANG H , LI D Y ,et al. Article edit evolution in wikipe-dia based on topology potential entropy[J]. Sciena ＆ Technology Re-view, 20142,30(4):71-74.
[15]	LI D . Artificial Intelligence with Uncertainty[M]. New York: CRC Press, 2007.
[16]	YE Q , ZHU T , HU D Y ,et al. Cell phone mini challenge award:social network accuracy-exploring temporal communication in mobile call graphs[A]. IEEE VAST 2008[C]. 2008.2007-2008.

节点	入度拓扑势	出度拓扑势	加权度	加权入度	加权出度	介数中心性	接近中心性	Page Rank	内容权威度	链接权威度	聚类系数	离心率	特征向量中心性
Sam	1	15	4	3	5	4	14	9	3	2	11	14	3
Bob	2	1	1	1	5	1	10	1	1	1	18	10	10
Domingo	3	21	8	2	21	16	21	2	2	21	1	21	1
Ted	4	21	17	3	21	16	21	3	3	21	20	21	5
Utrecht	5	12	4	3	5	7	12	10	3	2	11	12	6

数据集	中文名	节点数	边数	平均度	平均加权度	网络直径	图密度	模块度	社团个数	弱联通分量数目	强连通分量数目	平均聚类系数	平均路径长
Talking	谈天说地	2 070	6 627	3.201	3.879	10	0.02	0.403	68	48	1 158	0.068	3.912
Feeling	情感天空	3 019	13 050	4.323	5.671	11	0.001	0.335	48	28	1 665	0.06	3.816
Friends	缘来如此	1 206	2 021	1.676	1.934	18	0.001	0.664	118	92	901	0.029	5.228
Home	安居乐业	1 663	6 811	4.096	5.425	9	0.002	0.371	29	18	792	0.095	3.684
Joke	笑口常开	3 606	13 179	3.655	4.925	14	0.001	0.346	96	69	2 283	0.082	3.892
Picture	贴图秀	2 407	4 151	1.725	2.486	14	0.001	0.6	264	162	1 910	0.031	4.648

数据集	全网角色比例向量	全网角色分布向量
Talking	＜0.003,0.004,0.005,0.988＞	＜0.196,0.216,0.262,0.327＞
Feeling	＜0.002,0.002,0.001,0.995＞	＜0.196,0.221,0.253,0.330＞
Friends	＜0.003 3,0.011 6,0.021 6,0.964＞	＜0.194,0.203,0.280,0.323＞
Home	＜0.003,0.001,0.003,0.993＞	＜0.196,0.222,0.253,0.330＞
Joke	＜0.001,0.002,0.002,0.995＞	＜0.194,0.214,0.261,0.331＞
Picture	＜0,0.006,0.001,0.994＞	＜0.196,0.223,0.251,0.330＞

角色	数据集	节点	身份	总帖数	积分	生命值	该版块发帖数	该版块参与话题数	回复帖数	被回复帖数	最大出跳数	最大入度跳数
	Talking	11 574	用户	8 967	2 709	365	681	575	104	175	5	5
	Feeling	3 672	用户	3 897	2 254	365	648	229	468	544	2	6
桥接节点	Friends	836	管理员	13 544	1 271	135	206	155	133	41	3	10
	Home	523	管理员	46 703	5 604	666	419	151	407	260	5	1
	Joke	590	管理员	89 785	6 677	365	532	256	480	410	5	7
	Talking	598	管理员	24 108	4 293	365	129	100	107	53	2	6
	Feeling	14 458	用户	968	2 516	365	432	427	401	32	6	7
贡献节点	Friends	20 50	用户	1 102	1 872	365	12	8	5	3	10	12
	Home	565	管理员	2 718	1 274	365	136	109	128	46	5	1
	Joke	838	管理员	18 375	4 265	365	470	425	275	54	4	7
	Picture	836	管理员	13 544	1 271	135	643	578	478	51	4	7
	Talking	18 903	用户	3 521	2 337	365	95	51	43	63	1	6
	Feeling	590	管理员	89 785	6 677	365	271	182	253	176	1	6
接收节点	Friends	31 732	用户	22	16	134	2	1	1	59	1	10
	Home	18 997	用户	7 442	6 597	666	151	129	30	85	0	1
	Joke	5 011	用户	40 321	4 356	365	939	410	594	941	1	6
	Picture	302	用户	12 471	1 381	666	29	19	10	316	1	7

数据集	节点数	边数	平均度	平均加权度	网络直径	图密度	模块度	社团个数	平均聚类系数	平均路径长
第1天	370	633	1.711	2.668	24	0.005	0.74	22	0.016	8.957
第2天	373	617	1.654	2.584	29	0.004	0.768	24	0.007	11.646
第3天	374	627	1.676	2.548	35	0.004	0.748	22	0.005	10.151
第4天	374	625	1.671	2.709	32	0.004	0.756	22	0.007	10.302
第5天	373	627	1.681	2.657	22	0.005	0.754	22	0.006	7.567
第6天	373	629	1.686	2.582	33	0.005	0.747	19	0.008	9.383
第7天	367	603	1.643	2.55	22	0.004	0.755	27	0.006	8.063
第8天	365	622	1.704	2.753	30	0.005	0.748	20	0.01	9.433
第9天	374	632	1.69	2.626	24	0.005	0.751	24	0.012	9.616
第10天	384	662	1.724	2.708	33	0.005	0.748	21	0.004	10.808