Opinion leader recognition algorithm based on K-core decomposition in social networks

doi:10.11772/j.issn.1001-9081.2021010138

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (1): 26-35.DOI: 10.11772/j.issn.1001-9081.2021010138

Special Issue: 人工智能

• Artificial intelligence • Previous Articles Next Articles

Opinion leader recognition algorithm based on K-core decomposition in social networks

Meizi LI¹, Yifei MI¹, Qian ZHANG¹, Bo ZHANG¹^,²^,³()

^1.College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 201418，China
^2.Institute of Artificial Intelligence on Education，Shanghai Normal University，Shanghai 201418，China
^3.Shanghai Engineering Research Center of Intelligent Education and Bigdata （Shanghai Normal University），Shanghai 200234，China

Received:2021-01-26 Revised:2021-05-21 Accepted:2021-07-05 Online:2022-01-11 Published:2022-01-10
Contact: Bo ZHANG
About author:LI Meizi， born in 1979， Ph. D.， associate professor. Her research interests include social network analysis， data mining.
MI Yifei， born in 1997， M. S. candidate. Her research interests include social network analysis.
ZHANG Qian， born in 1994， M. S. Her research interests include social network analysis.
ZHANG Bo， born in 1978， Ph. D.， professor. His research interests include trust computation， social network analysis.
Supported by:
National Natural Science Foundation of China(61802258);Natural Science Foundation of Shanghai(18ZR1428300)

社交网络中基于K核分解的意见领袖识别算法

李美子¹, 米一菲¹, 张倩¹, 张波¹^,²^,³()

^1.上海师范大学信息与机电工程学院, 上海 201418
^2.上海师范大学人工智能教育研究院, 上海 201418
^3.上海智能教育大数据工程技术研究中心(上海师范大学), 上海 200234

通讯作者: 张波
作者简介:李美子（1979—），女，河北定州人，副教授，博士，CCF会员，主要研究方向：社交网络分析、数据挖掘
米一菲（1997—），女，河南许昌人，硕士研究生，CCF会员，主要研究方向：社交网络分析
张倩（1994—），女，河南信阳人，硕士，主要研究方向：社交网络分析
张波（1978—），男，江苏常州人，教授，博士，CCF高级会员，主要研究方向：信任计算、社交网络分析。
基金资助:
国家自然科学基金资助项目(61802258);上海市自然科学基金资助项目(18ZR1428300)

Abstract

Abstract:

In view of the high computational complexity of opinion leader mining in social networks， an opinion leader recognition algorithm based on K-core decomposition， named CandidateRank （CR）， was proposed. Firstly， the opinion leader candidate set in a social network was obtained based on K-core decomposition method， so as to reduce the data size of opinion leader recognition. Then， a user similarity concept including location similarity and neighbor similarity was proposed， and the user similarity was calculated by K-core value， the number of entries， average K-core change rate and the number of user followers， and the global influence of the user in the candidate set was calculated according to the user similarity. Finally， opinion leaders were recognized by ranking users in the opinion leader candidate set by the global influence. In the experiment， two evaluation indexes of user influence predicted by Independent Cascade Model （ICM） and centrality were used to evaluate the opinion leader set selected by the proposed algorithm on three real datasets with different sizes. The results show that the proposed algorithm has the average user influence for the selected Top-15 users of 21.442， which is higher than those of the other three algorithms. In addition， compared to four K-core-related algorithms in correlation index， the results show that CandidateRank algorithm performs better in general. In summary， CandidateRank algorithm improves the accuracy while reducing the computational complexity.

Key words: K-core decomposition, opinion leader, user similarity, social network, Independent Cascade Model (ICM)

摘要：

针对在社交网络中挖掘意见领袖时存在的计算复杂度高的难题，提出了一种基于K核分解的意见领袖识别算法CR。首先，基于K核分解方法获取社交网络中的意见领袖候选集，以缩小识别意见领袖的数据规模；然后，提出包括位置相似性和邻居相似性的用户相似性的概念，利用K核值、入度数、平均K核变化率和用户追随者个数计算用户相似性，并根据用户相似性对候选集中的用户计算全局影响力；最后，根据用户全局影响力对意见领袖候选集中的用户进行排序，从而识别意见领袖。在实验部分使用独立级联模型（ICM）预测的用户影响力和中心性两种评价指标在三个大小不同的真实数据集上对所提算法选出的意见领袖集进行评估，并将该算法与其他三种识别意见领袖的算法对比，结果表明该算法选出的影响力Top-15的用户平均影响力以21.442高于其他三个算法。另外，与四种与K核相关的算法做相关性指标对比的结果表明，CandidateRank算法总体来说效果较好。综上，CandidateRank算法在降低计算复杂度的同时提高了准确性。

关键词: K核分解, 意见领袖, 用户相似性, 社交网络, 独立级联模型

CLC Number:

TP391

Meizi LI, Yifei MI, Qian ZHANG, Bo ZHANG. Opinion leader recognition algorithm based on K-core decomposition in social networks[J]. Journal of Computer Applications, 2022, 42(1): 26-35.

李美子, 米一菲, 张倩, 张波. 社交网络中基于K核分解的意见领袖识别算法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 26-35.

Figures/Tables 10

Fig. 1 CandidateRank algorithm structure

Fig. 2 User role relationship

Tab. 1 Datasets for experiment

数据集	节点	边	最大入度数	最大K核值
1	320	526	33	15
2	4 039	88 234	251	115
3	49 613	43 576	707	15

Fig. 3 Performance of each algorithm on three datasets with p =0.02

Fig. 4 Performance of each algorithm on three datasets with p = 0.04

Fig. 5 Performance of each algorithm on three datasets with p = 0.06

Fig. 6 Performance of each algorithm on three datasets with p = 0.08

Tab. 2 Influence values of Top-15 nodes on Facebook dataset with p = 0.02

Top	CandidateRank	PageRank	DegreeRank	ELKSS
均值	21.442	16.875	12.221	13.965
1	44.524	44.193	44.193	44.193
2	20.406	24.534	24.534	45.037
3	21.990	45.037	45.037	24.534
4	21.407	14.103	14.103	2.173
5	20.960	10.160	10.160	5.337
6	22.306	8.351	2.173	7.051
7	19.883	7.738	5.337	19.315
8	19.490	11.158	1.058	21.182
9	18.679	11.296	1.661	7.653
10	20.220	9.351	3.074	10.552
11	18.334	12.319	6.953	8.514
12	18.648	11.946	7.051	1.058
13	18.417	12.519	7.517	8.209
14	17.796	20.048	8.351	1.214
15	18.582	10.373	2.118	3.464

Fig. 7 Centrality index values of four algorithms

Tab. 3 Correlation between ranking of opinion leaders calculated by four algorithms and ranking of influence of real nodes

数据集	（MDD， IC）	（ $C n c +$ ， IC）	（ELKSS， IC）	（CR， IC）
weibo1	0.048	0.409	0.238	0.414
Facebook	0.295	0.105	0.067	0.276
weibo2	0.215	0.087	0.108	0.296

Tab. 3 Correlation between ranking of opinion leaders calculated by four algorithms and ranking of influence of real nodes

数据集	（MDD， IC）	（ $C n c +$ ， IC）	（ELKSS， IC）	（CR， IC）
weibo1	0.048	0.409	0.238	0.414
Facebook	0.295	0.105	0.067	0.276
weibo2	0.215	0.087	0.108	0.296

References 25

1	徐郡明，朱福喜，刘世超，等. 改进LeaderRank算法的意见领袖挖掘［J］. 计算机工程与应用， 2015， 51（1）：110-114， 166. 10.3778/j.issn.1002-8331.1403-0032
	XU J M， ZHU F X， LIU S C， et al. Identifying opinion leaders by improved algorithm based on LeaderRank［J］. Computer Engineering and Applications， 2015， 51（1）： 110-114， 116. 10.3778/j.issn.1002-8331.1403-0032
2	WEN S， HAGHIGHI M S， CHEN C， et al. A sword with two edges： propagation studies on both positive and negative information in online social networks［J］. IEEE Transactions on Computers， 2015， 64（3）：640-653. 10.1109/tc.2013.2295802
3	王晨旭，管晓宏，秦涛，等. 微博消息传播中意见领袖影响力建模研究［J］. 软件学报， 2015， 26（6）：1473-1485. 10.13328/j.cnki.jos.004627
	WANG C X， GUAN X H， QIN T， et al. Modeling on opinion leader’s influence in microblog message propagation and its application［J］. Journal of Software， 2015， 26（6）： 1473-1485. 10.13328/j.cnki.jos.004627
4	YI Y X， ZHANG Z F， GAN C Q. The effect of social tie on information diffusion in complex networks［J］. Physical A： Statistical Mechanics and its Applications， 2018， 509：783-794. 10.1016/j.physa.2018.06.063
5	YANG L， QIAO Y F， LIU Z H， et al. Identifying opinion leader nodes in online social networks with a new closeness evaluation algorithm［J］. Soft Computing， 2018， 22（2）： 453-464. 10.1007/s00500-016-2335-3
6	VEGA-OLIVEROS D A， GOMES P S， MILIOS E E， et al. A multi-centrality index for graph-based keyword extraction［J］. Information Processing and Management， 2019， 56（6）： No.102063. 10.1016/j.ipm.2019.102063
7	李阅志，祝园园，钟鸣. 基于k-核过滤的社交网络影响最大化算法［J］. 计算机应用， 2018， 38（2）：464-470. 10.1007/978-3-319-91452-7_24
	LI Y Z， ZHU Y Y， ZHONG M. k-core filtered influence maximization algorithms in social networks［J］. Journal of Computer Applications， 2018， 38（2）： 464-470. 10.1007/978-3-319-91452-7_24
8	QIU L Q， DAI J L， LIU H Y， et al. Detecting opinion leaders in online social network using HybridRank algorithm［J］. Journal of Intelligent and Fuzzy Systems， 2018， 35（1）：513-522. 10.3233/jifs-169607
9	LI Y Y， MA S Q， ZHANG Y H， et al. An improved mix framework for opinion leader identification in online learning communities［J］. Knowledge-Based Systems， 2013， 43： 43-51. 10.1016/j.knosys.2013.01.005
10	GAO P Q， HUNG J， XU Y J. A k-core decomposition-based opinion leaders identifying method and clustering-based consensus model for large-scale group decision making［J］. Computers and Industrial Engineering， 2020， 150： No.106842. 10.1016/j.cie.2020.106842
11	LI J X， PENG W， LI T， et al. Social network user influence sense-making and dynamics prediction［J］. Expert Systems with Applications， 2014， 41（11）： 5115-5124. 10.1016/j.eswa.2014.02.038
12	AGHDAM S M， NAVIMIPOUR N J. Opinion leaders selection in the social networks based on trust relationships propagation［J］. Karbala International Journal of Modern Science， 2016， 2（2）： 88-97. 10.1016/j.kijoms.2016.02.002
13	XIA D G， MANKAD S， MICHAILIDIS G. Measuring influence of users in twitter ecosystems using a counting process modeling framework［J］. Technometrics， 2016， 58（3）： 360-370. 10.1080/00401706.2016.1142906
14	ZHOU J Y， ZHANG Y L， CHENG J. Preference-based mining of top-K influential nodes in social networks［J］. Future Generation Computer Systems， 2014， 31： 40-47. 10.1016/j.future.2012.06.011
15	陈志雄，王时绘，高榕. 基于情感倾向性分析的微博意见领袖识别模型［J］. 计算机科学， 2018， 45（5）： 168-175.
	CHEN Z X， WANG S H， GAO R. Recognition model of microblog opinion leaders based on sentiment orientation analysis［J］. Computer Science， 2018， 45（5）： 168-175.
16	WEI B， LIU J， WEI D J， et al. Weighted k-shell decomposition for complex networks based on potential edge weights［J］. Physical A： Statistical Mechanics and its Applications， 2015， 420： 277-283. 10.1016/j.physa.2014.11.012
17	YANG F， ZHANG R S， YANG Z， et al. Identifying the most influential spreaders in complex networks by an extended local K-Shell sum［J］. International Journal of Modern Physics C， 2017， 28（1）： No.1750014. 10.1142/s0129183117500140
18	ZENG A， ZHANG C J. Ranking spreaders by decomposing complex networks［J］. Physics Letters A， 2013， 377（14）： 1031-1035. 10.1016/j.physleta.2013.02.039
19	BAE J， KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood soreness［J］. Physical A： Statistical Mechanics and its Applications， 2014， 395： 549-559. 10.1016/j.physa.2013.10.047
20	LIU J G， REN Z M， GUO Q. Ranking the spreading influence in complex networks［J］. Physica A： Statistical Mechanics and its Applications， 2013， 392（18）： 4154-4159. 10.1016/j.physa.2013.04.037
21	HOU B N， YAO Y P， LIAO D S. Identifying all-around nodes for spreading dynamics in complex networks［J］. Physica A： Statistical Mechanics and its Applications， 2012， 391（15）： 4012-4017. 10.1016/j.physa.2012.02.033
22	TONG X L， LIU J G， WANG J P， et al. Ranking the spreading ability of nodes in network core［J］. International Journal of Modern Physics C， 2015， 26（5）： No.1550059. 10.1142/s012918311550059x
23	FREEMAN L C. Centrality in social networks conceptual clarification［J］. Social Networks， 1978/1979， 1（3）： 215-239. 10.1016/0378-8733(78)90021-7
24	JUN S， LEE S， KWON O， et al. Grid-based traffic vulnerability analysis by using betweenness centrality［J］. Journal of the Korean Physical Society， 2020， 77（7）：538-544. 10.3938/jkps.77.538
25	NEWMAN M. Networks： an introduction［J］. Astronomic Nachrichten， 2014， 327（8）： 741-743. 10.1007/978-1-84457-793-4_1

[1]	Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861.
[2]	Tao SUN, Zhangtian DUAN, Haonan ZHU, Peihao GUO, Heli SUN. Social event recommendation method based on unexpectedness metric [J]. Journal of Computer Applications, 2024, 44(3): 760-766.
[3]	Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838.
[4]	Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.
[5]	Li LI, Chunyan YANG, Jiangwen ZHU, Ronglei HU. User plagiarism identification scheme in social network under blockchain [J]. Journal of Computer Applications, 2024, 44(1): 242-251.
[6]	Shijie PENG, Hongmei CHEN, Lizhen WANG, Qing XIAO. Hybrid point-of-interest recommendation model based on geographic preference ranking [J]. Journal of Computer Applications, 2023, 43(8): 2448-2455.
[7]	Nannan SUN, Chunhui PIAO, Xinna MA. Group buying recommendation method based on social relationship and time-series information [J]. Journal of Computer Applications, 2023, 43(6): 1719-1729.
[8]	Yu YANG, Weiwei DUAN. Spectral clustering based dynamic community discovery algorithm in social network [J]. Journal of Computer Applications, 2023, 43(10): 3129-3135.
[9]	Liqing QIU, Fushuai QU. Emotional map of emergency based on sentiment analysis and influence evaluation [J]. Journal of Computer Applications, 2022, 42(5): 1330-1338.
[10]	Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG. Influence maximization algorithm based on node coverage and structural hole [J]. Journal of Computer Applications, 2022, 42(4): 1155-1161.
[11]	Qingqing WU, Lihua ZHOU, Xuanyi CUN, Guowang DU, Yiting JIANG. Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks [J]. Journal of Computer Applications, 2022, 42(3): 895-903.
[12]	Weifan XIE, Yan GUO, Guangsheng KUANG, Zhihua YU, Yuanhai XUE, Huawei SHEN. Popularity prediction method of Twitter topics based on evolution patterns [J]. Journal of Computer Applications, 2022, 42(11): 3364-3370.
[13]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[14]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[15]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.

Opinion leader recognition algorithm based on K-core decomposition in social networks

社交网络中基于K核分解的意见领袖识别算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 25

Related Articles 15

Recommended Articles

Metrics