《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (1): 26-35.DOI: 10.11772/j.issn.1001-9081.2021010138

• 人工智能 • 上一篇    下一篇

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

李美子1, 米一菲1, 张倩1, 张波1,2,3()   

  1. 1.上海师范大学 信息与机电工程学院, 上海 201418
    2.上海师范大学 人工智能教育研究院, 上海 201418
    3.上海智能教育大数据工程技术研究中心(上海师范大学), 上海 200234
  • 收稿日期:2021-01-26 修回日期:2021-05-21 接受日期:2021-07-05 发布日期:2022-01-11 出版日期:2022-01-10
  • 通讯作者: 张波
  • 作者简介:李美子(1979—),女,河北定州人,副教授,博士,CCF会员,主要研究方向:社交网络分析、数据挖掘
    米一菲(1997—),女,河南许昌人,硕士研究生,CCF会员,主要研究方向:社交网络分析
    张倩(1994—),女,河南信阳人,硕士,主要研究方向:社交网络分析
    张波(1978—),男,江苏常州人,教授,博士,CCF高级会员,主要研究方向:信任计算、社交网络分析。
  • 基金资助:
    国家自然科学基金资助项目(61802258);上海市自然科学基金资助项目(18ZR1428300)

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

Meizi LI1, Yifei MI1, Qian ZHANG1, Bo ZHANG1,2,3()   

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

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

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)

中图分类号: