research-article

An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs

Authors:

Zi-Ke ZhangAuthors Info & Claims

Volume 60, Issue 2

https://doi.org/10.1016/j.ipm.2022.103161

Published: 01 March 2023 Publication History

Abstract

Influence maximization (IM) has shown wide applicability in immense fields over the past decades. Previous researches on IM mainly focused on the dyadic relationship but lacked the consideration of higher-order relationship between entities, which has been constantly revealed in many real systems. An adaptive degree-based heuristic algorithm, i.e., Hyper Adaptive Degree Pruning (HADP) which aims to iteratively select nodes with low influence overlap as seeds, is proposed in this work to tackle the IM problem in hypergraphs. Furthermore, we extend algorithms from ordinary networks as baselines. Results on 8 empirical hypergraphs show that HADP surpasses the baselines in terms of both effectiveness and efficiency with a maximally 46.02% improvement. Moreover, we test the effectiveness of our algorithm on synthetic hypergraphs generated by different degree heterogeneity. It shows that the improvement of our algorithm effectiveness increases from 2.66% to 14.67% with the increase of degree heterogeneity, which indicates that HADP shows high performance especially in hypergraphs with high heterogeneity, which is ubiquitous in real-world systems.

Highlights

•

We explore the influence maximization problem in hypergraphs and propose an adaptive degree-based heuristic algorithm.

•

We compare our algorithm with state-of-the-art methods in various hypergraphs generated by real-world data, results show that our method displays both high effectiveness and efficiency.

•

The robustness test in synthetic hypergraphs shows our method achieves better performance in hypergraphs with high degree heterogeneity.

References

[1]

Amato F., Moscato V., Picariello A., Sperlí G., Influence maximization in social media networks using hypergraphs, in: International conference on green, pervasive, and cloud computing, Springer, 2017, pp. 207–221.

[2]

Antelmi A., Cordasco G., Spagnuolo C., Szufel P., Social influence maximization in hypergraphs, Entropy 23 (7) (2021) 796.

[3]

Battiston F., Cencetti G., Iacopini I., Latora V., Lucas M., Patania A., Young J.-G., Petri G., Networks beyond pairwise interactions: structure and dynamics, Physics Reports 874 (2020) 1–92.

[4]

Biswas T.K., Abbasi A., Chakrabortty R.K., An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks, Information Sciences 556 (2021) 27–48.

[5]

Borgs C., Brautbar M., Chayes J., Lucier B., Maximizing social influence in nearly optimal time, in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SIAM, 2014, pp. 946–957.

[6]

Bozorgi A., Haghighi H., Zahedi M.S., Rezvani M., INCIM: A community-based algorithm for influence maximization problem under the linear threshold model, Information Processing & Management 52 (6) (2016) 1188–1199.

[7]

Brin S., Page L., The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems 30 (1–7) (1998) 107–117.

Digital Library

[8]

Cencetti G., Battiston F., Lepri B., Karsai M., Temporal properties of higher-order interactions in social networks, Scientific Reports 11 (1) (2021) 7028.

[9]

Chen W., Wang C., Wang Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, in: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, 2010, pp. 1029–1038.

[10]

Cheng C.-H., Kuo Y.-H., Zhou Z., Outbreak minimization vs influence maximization: an optimization framework, BMC Medical Informatics and Decision Making 20 (1) (2020) 266.

[11]

Domingos P., Richardson M., Mining the network value of customers, in: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining, 2001, pp. 57–66.

Digital Library

[12]

Ferraz de Arruda G., Tizzani M., Moreno Y., Phase transitions and stability of dynamical processes on hypergraphs, Communications Physics 4 (1) (2021) 24.

[13]

Gao L., Wang H., Zhang Z., Zhuang H., Zhou B., HetInf: Social influence prediction with heterogeneous graph neural network, Frontiers in Physics (2022) 729.

[14]

Gong Y., Liu S., Bai Y., Efficient parallel computing on the game theory-aware robust influence maximization problem, Knowledge-Based Systems 220 (2021).

[15]

Goyal, A., Lu, W., & Lakshmanan, L. V. (2011). Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on world wide web (pp. 47–48).

[16]

Huang H., Shen H., Meng Z., Chang H., He H., Community-based influence maximization for viral marketing, Applied Intelligence 49 (6) (2019) 2137–2150.

[17]

Jhun B., Jo M., Kahng B., Simplicial SIS model in scale-free uniform hypergraph, Journal of Statistical Mechanics: Theory and Experiment 2019 (12) (2019).

[18]

Jung K., Heo W., Chen W., Irie: Scalable and robust influence maximization in social networks, in: 2012 IEEE 12th international conference on data mining, IEEE, 2012, pp. 918–923.

[19]

Kempe D., Kleinberg J., Tardos É., Maximizing the spread of influence through a social network, in: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, 2003, pp. 137–146.

Digital Library

[20]

Kumar S., Singhla L., Jindal K., Grover K., Panda B., IM-ELPR: Influence maximization in social networks using label propagation based community structure, Applied Intelligence 51 (11) (2021) 7647–7665.

[21]

Lee, G., Choe, M., & Shin, K. (2021). How Do Hyperedges Overlap in Real-World Hypergraphs?-Patterns, Measures, and Generators. In Proceedings of the web conference 2021 (pp. 3396–3407).

[22]

Lei, S., Maniu, S., Mo, L., Cheng, R., & Senellart, P. (2015). Online influence maximization. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 645–654).

[23]

Leskovec J., Krause A., Guestrin C., Faloutsos C., VanBriesen J., Glance N., Cost-effective outbreak detection in networks, in: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, 2007, pp. 420–429.

Digital Library

[24]

Li W., Li Y., Liu W., Wang C., An influence maximization method based on crowd emotion under an emotion-based attribute social network, Information Processing & Management 59 (2) (2022).

Digital Library

[25]

Li W., Ni L., Wang J., Wang C., Collaborative representation learning for nodes and relations via heterogeneous graph neural network, Knowledge-Based Systems 255 (2022).

Digital Library

[26]

Li W., Zhong K., Wang J., Chen D., A dynamic algorithm based on cohesive entropy for influence maximization in social networks, Expert Systems with Applications 169 (2021).

[27]

Lü L., Chen D., Ren X.-L., Zhang Q.-M., Zhang Y.-C., Zhou T., Vital nodes identification in complex networks, Physics Reports 650 (2016) 1–63.

[28]

Ma, A., & Rajkumar, A. (2022). Hyper-IMRANK: Ranking-based Influence Maximization for Hypergraphs. In 5th joint international conference on data science & management of data (9th ACM IKDD CODS and 27th COMAD) (pp. 100–104).

[29]

Morone F., Makse H.A., Influence maximization in complex networks through optimal percolation, Nature 524 (7563) (2015) 65–68.

[30]

Ouvrard X., Hypergraphs: an introduction and review, 2020, arXiv preprint arXiv:2002.05014.

[31]

Qiu L., Tian X., Zhang J., Gu C., Sai S., LIDDE: A differential evolution algorithm based on local-influence-descending search strategy for influence maximization in social networks, Journal of Network and Computer Applications 178 (2021).

[32]

Samir A.M., Rady S., Gharib T.F., LKG: A fast scalable community-based approach for influence maximization problem in social networks, Physica A: Statistical Mechanics and its Applications 582 (2021).

[33]

Singh S.S., Kumar A., Singh K., Biswas B., C2IM: Community based context-aware influence maximization in social networks, Physica A: Statistical Mechanics and its Applications 514 (2019) 796–818.

[34]

Singh S.S., Srivastva D., Verma M., Singh J., Influence maximization frameworks, performance, challenges and directions on social network: A theoretical study, Journal of King Saud University-Computer and Information Sciences (1319–1578) (2021).

[35]

St-Onge G., Iacopini I., Latora V., Barrat A., Petri G., Allard A., Hébert-Dufresne L., Influential groups for seeding and sustaining nonlinear contagion in heterogeneous hypergraphs, Communications Physics 5 (1) (2022) 25.

[36]

Stegehuis C., Peron T., Network processes on clique-networks with high average degree: the limited effect of higher-order structure, Journal of Physics: Complexity 2 (4) (2021).

[37]

Suo Q., Guo J.-L., Shen A.-Z., Information spreading dynamics in hypernetworks, Physica A: Statistical Mechanics and its Applications 495 (2018) 475–487.

[38]

Tanaka R., Scale-rich metabolic networks, Physical Review Letters 94 (16) (2005).

[39]

Wandelt S., Sun X., Feng D., Zanin M., Havlin S., A comparative analysis of approaches to network-dismantling, Scientific Reports 8 (1) (2018) 13513.

[40]

Wang B., Chen G., Fu L., Song L., Wang X., Drimux: Dynamic rumor influence minimization with user experience in social networks, IEEE Transactions on Knowledge and Data Engineering 29 (10) (2017) 2168–2181.

[41]

Wang C., Chen W., Wang Y., Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining and Knowledge Discovery 25 (3) (2012) 545–576.

[42]

Wang J., Ma X.-J., Xiang B.-B., Bao Z.-K., Zhang H.-F., Maximizing influence in social networks by distinguishing the roles of seeds, Physica A: Statistical Mechanics and its Applications (2022).

[43]

Wang Z., Sun C., Xi J., Li X., Influence maximization in social graphs based on community structure and node coverage gain, Future Generation Computer Systems 118 (2021) 327–338.

[44]

Xu X.-J., He S., Zhang L.-J., Dynamics of the threshold model on hypergraphs, Chaos. An Interdisciplinary Journal of Nonlinear Science 32 (2) (2022).

[45]

Young J.-G., Petri G., Peixoto T.P., Hypergraph reconstruction from network data, Communications Physics 4 (1) (2021) 135.

[46]

Zhan X.-X., Li Z., Masuda N., Holme P., Wang H., Susceptible-Infected-Spreading-based network embedding in static and temporal networks, EPJ Data Science 9 (1) (2020) 30.

[47]

Zhang Y., Shi Z., Feng D., Zhan X.-X., Degree-biased random walk for large-scale network embedding, Future Generation Computer Systems 100 (2019) 198–209.

[48]

Zhu J., Zhu J., Ghosh S., Wu W., Yuan J., Social influence maximization in hypergraph in social networks, IEEE Transactions on Network Science and Engineering 6 (4) (2018) 801–811.

Cited By

Wang JCao ZXie CLi YLiu JGao Z(2025)DGN: influence maximization based on deep reinforcement learningThe Journal of Supercomputing10.1007/s11227-024-06621-981:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06621-9
Xie JZhang SLiu CZhan X(2024)Fair Influence Maximization in HypergraphsProceedings of the Third International Workshop on Social and Metaverse Computing, Sensing and Networking10.1145/3698387.3699995(8-14)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3698387.3699995
Theocharidis KKarras PTerrovitis MSkiadopoulos SLauw H(2024)Adaptive Content-Aware Influence Maximization via Online Learning to RankACM Transactions on Knowledge Discovery from Data10.1145/365198718:6(1-35)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3651987
Show More Cited By

Index Terms

An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs

Index terms have been assigned to the content through auto-classification.

Recommendations

3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Chvatal, Rodl, Szemeredi and Trotter [V. Chvatal, V. Rodl, E. Szemeredi, W.T. Trotter Jr., The Ramsey number of a graph with a bounded maximum degree, J. Combin. Theory Ser. B 34 (1983) 239-243] proved that the Ramsey numbers of graphs of bounded ...
Erdős-Hajnal-type theorems in hypergraphs

The Erdos-Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n^@d^(^H^), where @d(H)>0 depends only on the ...
On 2-Colorings of Hypergraphs

In this article, we continue the study of 2-colorings in hypergraphs. A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let Hk denote the class of all k-uniform k-regular hypergraphs. It is known see ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Processing and Management: an International Journal

Information Processing and Management: an International Journal Volume 60, Issue 2

Mar 2023

1443 pages

ISSN:0306-4573

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 March 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang JCao ZXie CLi YLiu JGao Z(2025)DGN: influence maximization based on deep reinforcement learningThe Journal of Supercomputing10.1007/s11227-024-06621-981:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06621-9
Xie JZhang SLiu CZhan X(2024)Fair Influence Maximization in HypergraphsProceedings of the Third International Workshop on Social and Metaverse Computing, Sensing and Networking10.1145/3698387.3699995(8-14)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3698387.3699995
Theocharidis KKarras PTerrovitis MSkiadopoulos SLauw H(2024)Adaptive Content-Aware Influence Maximization via Online Learning to RankACM Transactions on Knowledge Discovery from Data10.1145/365198718:6(1-35)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3651987
Chen YWang XChen CSerra ESpezzano F(2024)Hyperedge Importance Estimation via Identity-aware Hypergraph Attention NetworkProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679685(334-343)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679685
Ju WChen YChen LLi B(2024)Locating influence sources in social network by senders and receivers spaces mappingExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123327248:COnline publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123327
Tang JZhu HHan LSong S(2024)Identifying top-k influential nodes in social networks: a discrete hybrid optimizer by integrating butterfly optimization algorithm with differential evolutionThe Journal of Supercomputing10.1007/s11227-024-06215-580:13(19624-19668)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11227-024-06215-5
Venunath MSujatha PKoti P(2024)Identification of influential users in social media network using golden ratio optimization methodSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09218-128:3(2207-2222)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00500-023-09218-1
Genetti SRibaga ECunegatti ELotito QIacca G(2024)Influence Maximization in Hypergraphs Using Multi-Objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_14(217-235)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_14
Gong YWang MLiang WHu FZhang Z(2023)UHIRInformation Sciences: an International Journal10.1016/j.ins.2023.119284644:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.119284
Bu FLee GShin K(2023)Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applicationsData Mining and Knowledge Discovery10.1007/s10618-023-00956-237:6(2389-2437)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10618-023-00956-2

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents