Influence Maximization Algorithm Based on Local Domain

doi:10.19678/j.issn.1000-3428.0062160

Abstract

Abstract: Measures of user influence are at the core of the influence maximization problem.As these measures relate to network topology, they may be classified as global indicators or local indicators.Global indicators rely on the complete network topology to calculate the influence of nodes, and incur a high time complexity.In contrast, local indicators generally ignore or weaken the self-loop and multilateral phenomena in the network, resulting in an incomplete measurement of the influence of nodes, which affects the final dissemination range of information.Using the principle of three degrees of separation, an influence maximization algorithm based on local domain is proposed in this study.This algorithm first constructs a generated graph by making full use of the edges, starting at and ending with the same interconnected nodes.Then, it generates a local domain for each node and approximates each node's global influence, calculated by the topology of its local domain.Finally, the algorithm conducts seed selection by considering the influence of each node, as well as the influence overlap ratio factor of a seed set.Experimental results on real datasets show that, compared with algorithms such as MaxDegree and PageRank, the proposed algorithm can effectively identify high-influence node groups, improve the scope of information dissemination, and incur lower time complexity.

Key words: influence maximization, local influence, global influence, three degrees of separation, influence overlap

摘要： 用户影响力度量是影响力最大化问题的核心，与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标，其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高，局部性指标通常忽略或弱化了网络中的自环和多边现象，导致对节点影响力的度量不全面，限制信息最终传播范围。结合三度分隔原理，提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象，根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域，使用节点在局部域内的影响力近似其在全局范围内的影响力，并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子，根据重叠比因子决定是否将此候选种子节点选作种子节点，控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明，与MaxDegree、PageRank等算法相比，该算法能有效识别高影响力节点群体，扩大信息传播范围，且具有较低的时间复杂度。

关键词: 影响力最大化, 局部影响力, 全局影响力, 三度分隔, 影响力重叠

CLC Number:

TP393

SHEN Jiquan, LIN Shuai, LI Zhiying. Influence Maximization Algorithm Based on Local Domain[J]. Computer Engineering, 2022, 48(7): 22-28.

沈记全, 林帅, 李志莹. 基于局部域的影响力最大化算法[J]. 计算机工程, 2022, 48(7): 22-28.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0062160

http://www.ecice06.com/EN/Y2022/V48/I7/22

Figures/Tables 6

References

[1] TANG X N, YANG C C.Ranking user influence in healthcare social media[J].ACM Transactions on Intelligent Systems and Technology, 2012, 3(4):1-21.
[2] HUANG J M, CHENG X Q, SHEN H W, et al.Exploring social influence via posterior effect of word-of-mouth recommendations[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining.New York, USA:ACM Press, 2012:573-582.
[3] BADASHIAN A S, STROULIA E.Measuring user influence in GitHub:the million follower fallacy[C]//Proceedings of the 3rd International Workshop on CrowdSourcing in Software Engineering.Washington D.C., USA:IEEE Press, 2016:15-21.
[4] DOMINGOS P, RICHARDSON M.Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2001:57-66.
[5] 陶天一, 王清钦, 付聿炜, 等.基于知识图谱的金融新闻个性化推荐算法[J].计算机工程, 2021, 47(6):98-103, 114. TAO T Y, WANG Q Q, FU Y W, et al.Personalized recommendation algorithm for financial news based on knowledge graph[J].Computer Engineering, 2021, 47(6):98-103, 114.(in Chinese)
[6] WADHERA T.Brain network topology unraveling epilepsy and ASD association:automated EEG-based diagnostic model[J].Expert Systems with Applications, 2021, 186:115762.
[7] FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry, 1977, 40(1):35.
[8] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks, 1978, 1(3):215-239.
[9] HAGE P, HARARY F.Eccentricity and centrality in networks[J].Social Networks, 1995, 17(1):57-63.
[10] FREEMAN L C, BORGATTI S P, WHITE D R.Centrality in valued graphs:a measure of betweenness based on network flow[J].Social Networks, 1991, 13(2):141-154.
[11] KATZ L.A new status index derived from sociometric analysis[J].Psychometrika, 1953, 18(1):39-43.
[12] ESTRADA E, HATANO N.Communicability in complex networks[J].Physical Review E:Statistical, Nonlinear, and Soft Matter Physics, 2008, 77(3):036111.
[13] BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].The Journal of Mathematical Sociology, 1972, 2(1):113-120.
[14] CHEN D B, LÜ L, SHANG M S, et al.Identifying influential nodes in complex networks[J].Physica A:Statistical Mechanics and Its Applications, 2012, 391(4):1777-1787.
[15] BONACICH P.Power and centrality:a family of measures[J].American Journal of Sociology, 1987, 92(5):1170-1182.
[16] 尼古拉斯·克里斯塔基斯, 詹姆斯·富勒.大连接:社会网络是如何形成的以及对人类现实行为的影响[M].北京:中国人民大学出版社, 2013. CHRISTAKIS N A, FOWLER J H.Connected:the surprising power of our social networks and how they shape our lives[M].Beijing:China Renmin University Press, 2013.(in Chinese)
[17] 孔秀琼, 袁正中, 蔡萍.带自环的无向网络的同步研究[J].闽南师范大学学报(自然科学版), 2019, 32(3):26-30. KONG X Q, YUAN Z Z, CAI P.Synchronization of undirected complex network with self-loop[J].Journal of Minnan Normal University(Natural Science), 2019, 32(3):26-30.(in Chinese)
[18] KEMPE D, KLEINBERG J, TARDOS É.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2003:137-146.
[19] 王怡, 梁循, 付虹蛟, 等.社会网络中信息的扩散机理及其定量建模[J].中国管理科学, 2017, 25(12):147-157. WANG Y, LIANG X, FU H J, et al.Mechanism and quantity modeling of information diffusion in social networks[J].Chinese Journal of Management Science, 2017, 25(12):147-157.(in Chinese)
[20] BRIN S, PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7):107-117.
[21] ZHANG X H, LI Z Y, QIAN K, et al.Influential node identification in a constrained greedy way[J].Physica A:Statistical Mechanics and Its Applications, 2020, 557:124887.
[22] 夏欣, 马闯, 张海峰.基于改进的度折扣方法研究社交网络影响力最大化问题[J].电子科技大学学报, 2021, 50(3):450-458. XIA X, MA C, ZHANG H F.An improved degree discount approach for influence maximization in social networks[J].Journal of University of Electronic Science and Technology of China, 2021, 50(3):450-458.(in Chinese)

Please choose a citation manager

Content to export