融合高阶信息的社交网络重要节点识别算法

doi:10.11959/j.issn.1000-436x.2019198

Abstract

Abstract:

Identifying vital nodes is a basic problem in complex network research.The existing theoretical framework,mainly considered from the lower-order structure of node-based and edge-based relations often ignores important factors such as interactivity and transitivity between multiple nodes.To identify vital nodes more accurately,the motif,the high-er-order structure of the network,was studied as the basic unit.Firstly,a notion of higher-order degree of nodes in a com-plex network was proposed.Then,the higher-order structure and lower-order structure of nodes were fused into evidence theory.A semi-local identifying vital nodes algorithm fusing higher-order information of nodes was designed.The results of experiments on three real social networks show that the proposed algorithm can identify vital nodes more accurately in the network than the existing methods which only focus on the low-order structure.

Key words: vital node, motif, higher-order network, evidence theory, social network

CLC Number:

TP181，TP391

Guanghui YAN, Meng ZHANG, Hao LUO, Shikui LI, Ting LIU. Identifying vital nodes algorithm in social networks fusing higher-order information[J]. Journal on Communications, 2019, 40(10): 109-118.

Figures/Tables 13

$M$	Wiki-vote	Advogato	soc-Epinions1
$M_{1}$	6 795	63	7 656
$M_{2}$	17 667	2 230	84 384
$M_{3}$	15 275	3 162	328 076
$M_{4}$	2 119	1 992	160 097
$M_{5}$	462 715	4 262	531 325
$M_{6}$	45 559	3 019	281 093
$M_{7}$	58 259	3 564	231 850

References 26

[1]	张静, 唐杰 . 社会影响力分析综述[J]. 中国科学:信息科学, 2017,47(8): 967-979.
	ZHANG J , TANG J . Survey of social influence analysis and modeling[J]. SCIENTIA SINICA Informationis, 2017,47(8): 967-979.
[2]	韩忠明, 陈炎, 刘雯 ,等. 社会网络节点影响力分析研究[J]. 软件学报, 2017,28(1): 84-104.
	HAN Z M , CHEN Y , LIU W ,et al. Research on node influence analysis in social networks[J]. Journal of Software, 2017,28(1): 84-104.
[3]	BONACICH P F . Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972,2(1): 113-120.
[4]	任晓龙, 吕琳媛 . 网络重要节点排序方法综述[J]. 科学通报, 2014,59(13): 1175-1197.
	REN X L , LYU L Y . Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014,59(13): 1175-1197.
[5]	WEI D , DENG X , ZHANG X ,et al. Identifying influential nodes in weighted networks based on evidence theory[J]. Physica A:Statistical Mechanics and its Applications, 2013,392(10): 2564-2575.
[6]	MICHAEL J M . Applied network analysis:a method logical introduc tion[M]. New York: Sage PublicationsPress, 1983.
[7]	FREEMAN L C . A set of measures of centrality based on betweenness[J]. Sociometry, 1977,40(1): 35-41.
[8]	FREEMAN L C . Centrality in social networks conceptual clarification[J]. Social Networks, 1978,1(3): 215-239.
[9]	BRIN S , PAGE L . The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998: 107-117.
[10]	LYU L Y , ZHANG Y C , YEUNG C H ,et al. Leaders in social networks,the delicious case[J]. PLOS ONE, 2011,6(6): 1-9.
[11]	ALON U . Network motifs:theory and experimental approaches[J]. Nature Reviews Genetics, 2007,8(6): 450-461.
[12]	PR?ULJ N , CORNEIL D G , JURISICA I . Modeling interactome:scale-free or geometric?[J]. Bioinformatics, 2004,20(18): 3508-3515.
[13]	MILO R , SHEN-ORR S , ITZKOVITZ S ,et al. Network motifs:simple building blocks of complex networks[J]. Science, 2002,298(5594): 824-827.
[14]	SHEN-ORR S , MILO R , MANGAN S ,et al. Network motifs in the transcriptional regulation network of escherichia coli[J]. Nature Genetics, 2002,31(1): 64-68.
[15]	BENSON A R , GLEICH D F , LESKOVEC J . Higher-order organization of complex networks[J]. Science, 2016,353(6295): 163-166.
[16]	YIN H , BENSON A R , LESKOVEC J ,et al. Local higher-order graph clustering[C]// The 23rd ACM SIGKDD International Conference. 2017: 555-564.
[17]	BENSON A R . Tools for higher-order network analysis[D]. Palo Alto:Stanford University, 2018.
[18]	DAVIS J , LEINHARDT S . The structure of positive interpersonal relations in small groups[J]. J Berger Sociological Theories in Progress, 1967:54.
[19]	WASSERMAN S . Social network analysis methods and applications[J]. Contemporary Sociology, 1995,91(435): 219-220.
[20]	SCHANK T , WAGNER D . Finding,counting and listing all triangles in large graphs,an experimental study[M]. Heidelberg: Springer Berlin HeidelbergPress, 2005.
[21]	蒋雯, 邓鑫洋 . D-S证据理论信息建模与应用[M]. 北京: 科学出版社, 2018.
	JIANG W , DENG X Y . Information modeling and application of D-S evidence theory[M]. Beijing: Science PressPress, 2018.
[22]	SHAFER G . A mathematical theory of evidence by glenn shafer[J]. Journal of the American Statistical Association, 1978,73(363): 677-678.
[23]	CHEN D B , LYU L Y , SHANG M S ,et al. Identifying influential nodes in complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2012,391(4): 1777-1787.
[24]	GAO C , WEI D J , HU Y ,et al. A modified evidential methodology of identifying influential nodes in weighted networks[J]. Physica A:Statistical Mechanics and its Applications, 2013,392(21): 5490-5500.
[25]	周涛, 傅忠谦, 牛永伟 ,等. 复杂网络上传播动力学研究综述[J]. 自然科学进展, 2005,15(5): 513-518.
	ZHOU T , FU Z Q , NIU Y W ,et al. A survey of propagation dynamics in complex networks[J]. Progress in Natural Science, 2005,15(5): 513-518.
[26]	王庆 . 自我中心网络的结构建模与研究[D]. 北京:北京邮电大学, 2017.
	WANG Q . On ego network modeling and analysis[D]. Beijing:Beijing University of Posts and Telecommunications, 2017.

Metrics

Recommended 0

No Suggested Reading articles found!

节点	k_i	HD_i	m_i(h)	m_i(l)	HEC(i)
1	5	3	0.661 0	0.260 8	0.273 6
2	4	4	0.900 6	0.018 3	0.370 5
3	0	1	0	0.960 5	0
4	0	1	0	0.960 5	0
5	0	1	0	0.960 5	0
6	2	2	0.211 3	0.736 2	0.087 6
7	2	1	0.003 6	0.953 8	0.002 1
8	4	2	0.314 1	0.612 3	0.133 1
9	4	2	0.314 1	0.612 3	0.133 1
10	0	1	0	0.960 5	0

算法	时间复杂度
DC	O (n)
BC	O( 3n )
CC	O( 3n )
HEC	O(m ^1.5+n)
HESC	O(m ^1.5+n<k>²)

数据集	节点数	边数	M ₁～M₇的总数量
Wiki-vote	7 100	103 700	608 400
Advogato	6 500	51 100	18 300
soc-Epinions1	75 900	508 800	1 600 000

TopN	DC	CC	BC	HEC	HESC
Top1	18	18	44	18	645
Top2	645	737	763	645	634
Top3	634	136	634	634	44
Top4	763	790	2 066	143	71 399
Top5	143	143	645	790	763
Top6	737	1 719	1 409	44	637
Top7	44	118	546	136	34
Top8	790	128	2 969	1 719	145
Top9	34	40	737	737	1 059
Top10	136	1 179	2 118	1 179	824

Identifying vital nodes algorithm in social networks fusing higher-order information

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 26

Related Articles 15

Metrics

Recommended 0

[1]	Yu DONG, Youpeng ZHANG. Conflict evidence combination method based on clustering weighting [J]. Journal on Communications, 2023, 44(3): 157-163.
[2]	Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network [J]. Journal on Communications, 2022, 43(8): 151-163.
[3]	Xin WANG, Wei FU. Strong measurement method of evidence conflict based on earth mover’s distance [J]. Journal on Communications, 2022, 43(5): 204-213.
[4]	Tao PENG, Wentao ZHONG, Guojun WANG, Entao LUO, Jinbo XIONG, Yining LIU, Wang Hao. Privacy-preserving precise profile matching in mobile social network [J]. Journal on Communications, 2022, 43(11): 90-103.
[5]	Xinglin GUO, Zhenxiao SUN, Yuyao ZHOU, Lianzhi QI, Yi ZHANG. Evidence conflict measurement method based on Pignistic probability transformation and singular value decomposition [J]. Journal on Communications, 2021, 42(4): 150-157.
[6]	Zhen LIU,Na’na WANG,Xiaodong WANG,Yongqi SUN. Spectral clustering and embedding-enhanced POI recommendation in location-based social network [J]. Journal on Communications, 2020, 41(3): 197-206.
[7]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[8]	Zhiguo SUN, Xinyue REN, Zengmao CHEN, Ming DIAO. Cooperative spectrum sensing method and performance analysis based on similarity between evidences [J]. Journal on Communications, 2020, 41(12): 139-147.
[9]	Jing CHEN,Ziyi QI. Research on social network influence maximization algorithm based on time sequential relationship [J]. Journal on Communications, 2020, 41(10): 211-221.
[10]	Junlei BI,Zhiyuan LI. Time-variant interest community based query message routing algorithm in opportunity social network [J]. Journal on Communications, 2019, 40(9): 86-94.
[11]	Fenghua LI,Zhe SUN,Ben NIU,Jin CAO,Hui LI. Privacy-preserving photo sharing framework cross different social network [J]. Journal on Communications, 2019, 40(7): 1-13.
[12]	Haiping HUANG,Kai WANG,Xiong TANG,Dongjun ZHANG. Differential privacy protection scheme based on edge betweenness model [J]. Journal on Communications, 2019, 40(5): 88-97.
[13]	Xiaoping YANG,Weijian LIAN,Mengjie LI,Zhihong QIAN. Evidence combination method based on Pignistic function transformation and correlation coefficient [J]. Journal on Communications, 2019, 40(3): 73-79.
[14]	Xiaomeng WANG, Binxing FANG, Hongli ZHANG, Xing WANG. TSL:predicting popularity of Facebook content based on tie strength [J]. Journal on Communications, 2019, 40(10): 1-9.
[15]	Yu FU, Yihan YU, Xiaoping WU. Differential privacy protection technology and its application in big data environment [J]. Journal on Communications, 2019, 40(10): 157-168.