基于Motif的社交网络用户影响力排序方法研究
Research on Social Network User Impact Ranking Method Based on Motif
DOI: 10.12677/CSA.2020.106114, PDF,   
作者: 曲贤菲, 田朝霞, 陈 旭：大连海事大学信息科学技术学院，辽宁 大连
关键词: LeaderRank算法；社交网络；高阶关系；排序方法；LeaderRank Algorithm； Social Network； Higher-Order Relationship； Ranking Method
摘要: LeaderRank已被广泛地用于衡量社交网络中用户的影响力或重要性的排序算法，但传统的LeaderRank仅利用基于边的关系，而忽略由少量节点组成的子图捕获的高阶关系。在本文中，我们提出一种基于Motif的LeaderRank (MLR)算法，将Motif的高阶关系合并到LeaderRank算法中，提高社交网络用户影响力的排序效果。我们在Twitter数据集上进行实验，结果不仅表明MLR算法的可行性，并且还显著提高了在社交网络用户影响力排序的准确性。除了与基线算法比较之外，还对MLR算法的参数进行分析，表明在社交网络中对用户影响力排序时，MLR算法比LeaderRank要更好。
Abstract: LeaderRank has been widely used in ranking algorithms to measure the influence or importance of users in social networks, but traditional LeaderRank only uses edge-based relationships and ignores high-order relationships captured by a subgraph composed of a small number of nodes. In this paper, we propose a Motif-based LeaderRank (MLR) algorithm, which incorporates the higher-order relationships of Motif into the LeaderRank algorithm to improve the ranking effect of social network user influence. We perform experiments on the Twitter dataset, and the results not only show the feasibility of the MLR algorithm, but also significantly improve the accuracy of the ranking of user influence in social networks. In addition to comparing with the baseline algorithm, the parameters of the MLR algorithm are also analyzed, which shows that the MLR algorithm is better than LeaderRank when ranking user influence in social networks.
文章引用：曲贤菲, 田朝霞, 陈旭. 基于Motif的社交网络用户影响力排序方法研究[J]. 计算机科学与应用, 2020, 10(6): 1098-1112. https://doi.org/10.12677/CSA.2020.106114

参考文献

[1] Song, X., Chi, Y., Hino, K., et al. (2007) Identifying Opinion Leaders in the Blogosphere. Proceedings of the 16th ACM Conference on Information and Knowledge Management, CIKM 2007, Lisbon, 6-10 November 2007, 971-974. [Google Scholar] [CrossRef] 
[2] Tang, J., Sun, J., Wang, C., et al. (2009) Social Influence Analysis in Large-Scale Networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 28 June-1 July 2009, 807-816. [Google Scholar] [CrossRef] 
[3] Xiang, B., Liu, Q., Chen, E., et al. (2013) PageRank with Priors: An Influence Propagation Perspective. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, AAAI Press, Palo Alto, 2740-2746.
[4] Wang, Y., Wang, X., Tang, J., et al. (2015) Modeling Status Theory in Trust Prediction. AAAI, 1875-1881.
[5] Page, L., Brin, S., Motwani, R. and Winograd, T. (1999) The Pagerank Citation Ranking: Bringing Order to the Web. Proceedings of the 7th Interna-tional World Wide Web Conference, Brisbane, 1998, 161-172.
[6] Lü, L.Y., Zhang, Y.-C., Yeung, C.H. and Zhou, T. (2011) Leaders in Social Networks, the Delicious Case. PLoS ONE, 6, e21202. [Google Scholar] [CrossRef] [PubMed]
[7] Jiang, X., Sun, X. and Zhuge, H. (2013) Graph-Based Algo-rithms for Ranking Researchers: Not All Swans Are White! Scientometrics, 96, 743-759. [Google Scholar] [CrossRef] 
[8] 邓启平, 王小梅. 利用LeaderRank识别有影响力的作者[J]. 现代图书情报技术, 2015, 31(9): 60-67.
[9] 徐郡明, 朱福喜, 刘世超, 等. 改进LeaderRank算法的意见领袖挖掘[J]. 计算机工程与应用, 2015(1): 110-114.
[10] Zhang, Z.H., Jiang, G.P., Song, Y.R., et al. (2017) An Improved Weighted LeaderRank Algorithm for Identifying Influential Spreaders in Complex Networks. An Improved Weighted LeaderRank Algorithm for Identifying Influential Spreaders in Complex Networks. IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Com-puting (EUC), Guangzhou, 21-24 July 2017. [Google Scholar] [CrossRef] 
[11] Bakshy, E., Hofman, J.M., Mason, W.A., et al. (2015) Every-one’s an Influencer: Quantifying Influence on Twitter. Proceedings of the 4th ACM International Conference on Web Search and Data Mining, Hong Kong, 9-12 February 2011.
[12] 顾亦然, 朱梓嫣. 基于LeaderRank和节点相似度的复杂网络重要节点排序算法[J]. 电子科技大学学报, 2017, 46(2): 441-448.
[13] Watts, D.J. and Strogatz, S.H. (1998) Collective Dynamics of Small World Networks. Nature, 393, 440-442. [Google Scholar] [CrossRef] [PubMed]
[14] Sen, P., Dasgupta, S., Chatterjee, A., et al. (2003) Small-World Properties of the Indian Railway Network. Physical Review E, 67, 036106. [Google Scholar] [CrossRef] 
[15] Barabási, A.-L. and Albert, R. (1999) Emergence of Scaling in Random Networks. Science, 286, 509-512. [Google Scholar] [CrossRef] [PubMed]
[16] Barabási, A.-L., Albert, R. and Jeong, H. (2000) Scale-Free Characteristics of Random Networks: The Topology of the World-Wide Web. Physica A, 281, 69-77. [Google Scholar] [CrossRef] 
[17] Milo, R., Shen-Orr, S., Itzkovitz, S., et al. (2002) Network Motifs: Simple Building Blocks of Complex Networks. Science, 298, 824-827. [Google Scholar] [CrossRef] [PubMed]
[18] Ugander, J., Backstrom, L. and Kleinberg, J.M. (2013) Sub-graph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections. Proceedings of the 22nd international conference on World Wide Web, Rio de Janeiro, May 2013, 1307-1318. [Google Scholar] [CrossRef] 
[19] Rotabi, R., Kamath, K., Kleinberg, J., et al. (2017) Detecting Strong Ties Using Network Motifs. Proceedings of the 26th International Conference on World Wide Web, Perth, 3-7 April 2017, 983-992. [Google Scholar] [CrossRef] 
[20] Wang, P., Lü, J.H. and Yu, X. (2014) Identification of Important Nodes in Directed Biological Networks: A Network Motif Approach. PLoS ONE, 9, e106132. [Google Scholar] [CrossRef] [PubMed]
[21] Nataša, P. (2007) Biological Network Comparison Using Graphlet Degree Distribution. Bioinformatics, 23, e177-e183.
[22] Ahmed, N.K., Neville, J., Rossi, R.A., et al. (2015) Efficient Graphlet Counting for Large Networks. 2015 IEEE International Conference on Data Mining (ICDM). 2015 IEEE International Conference on Data Mining, Atlantic City, 14-17 November 2015. [Google Scholar] [CrossRef] 
[23] Jha, M., Seshadhri, C. and Pinar, A. (2014) Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts. Proceedings of the 24th International Conference on World Wide Web, Florence, 18-22 May 2015, 495-505. [Google Scholar] [CrossRef] 
[24] Han, G. and Sethu, H. (2016) Waddling Random Walk: Fast and Accurate Mining of Motif Statistics in Large Graphs. 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, 12-15 December 2016. [Google Scholar] [CrossRef] 
[25] Benson, A.R., Gleich, D.F. and Leskovec, J. (2016) Higher-Order Organization of Complex Networks. Science, 353, 163-166. [Google Scholar] [CrossRef] [PubMed]
[26] 许平华, 胡文斌, 邱振宇, 等. 节点不对称转移概率的网络社区发现算法[J]. 软件学报, 2019, 30(12): 3829-3845.