short-paper

Hyper-IMRANK: Ranking-based Influence Maximization for Hypergraphs

Authors:

Arun RajkumarAuthors Info & Claims

CODS-COMAD '22: Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD)

Pages 100 - 104

https://doi.org/10.1145/3493700.3493706

Published: 08 January 2022 Publication History

Abstract

Influence maximization algorithms have found tremendous success in applications such as social media viral marketing. However, in several applications, the nature of relationships among participating entities cannot be accurately described only using pairwise interactions. To model group interactions, we consider the influence maximization problem in hypergraphs. Specifically, we consider a recently proposed diffusion model - HyperCascade which generalizes the standard independent cascade model. We propose a novel ranking based algorithm called Hyper-IMRANK to select highly influential nodes under this model. We demonstrate the superior performance of our algorithms in real world as well as synthetic datasets.

References

[1]

Chen Avin, Zvi Lotker, Yinon Nahum, and David Peleg. 2019. Random preferential attachment hypergraph. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 398–405.

Digital Library

[2]

Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences (2018). https://doi.org/10.1073/pnas.1800683115

[3]

Hrishikesh Bharadwaj Chakrapani, Smruti Chourasia, Sibasish Gupta, Rishin Haldar, 2021. Effective utilisation of influence maximization technique for the identification of significant nodes in breast cancer gene networks. Computers in Biology and Medicine 133 (2021), 104378.

Digital Library

[4]

Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient Influence Maximization in Social Networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Paris, France) (KDD ’09). Association for Computing Machinery, New York, NY, USA, 199–208. https://doi.org/10.1145/1557019.1557047

Digital Library

[5]

Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In 2010 IEEE international conference on data mining. IEEE, 88–97.

Digital Library

[6]

Suqi Cheng, Huawei Shen, Junming Huang, Wei Chen, and Xueqi Cheng. 2014. IMRank: influence maximization via finding self-consistent ranking. In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. 475–484.

Digital Library

[7]

Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, and Xueqi Cheng. 2013. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 509–518.

Digital Library

[8]

Sainyam Galhotra, Akhil Arora, and Shourya Roy. 2016. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In Proceedings of the 2016 International Conference on Management of Data. 743–758.

Digital Library

[9]

Varun Gangal, Balaraman Ravindran, and Ramasuri Narayanam. 2016. HEMI: Hyperedge Majority Influence Maximization. arXiv preprint arXiv:1606.05065(2016).

[10]

Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web. 47–48.

Digital Library

[11]

Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In 2011 IEEE 11th international conference on data mining. IEEE, 211–220.

Digital Library

[12]

Kyomin Jung, Wei Chen, and Wooram Heo. 2011. IRIE: A scalable influence maximization algorithm for independent cascade model and its extensions. Technical Report.

[13]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137–146.

Digital Library

[14]

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 420–429.

Digital Library

[15]

Mark EJ Newman. 2011. The structure of scientific collaboration networks. In The Structure and Dynamics of Networks. Princeton University Press, 221–226.

[16]

Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. In AAAI. Citeseer, 138–144.

[17]

Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June (Paul) Hsu, and Kuansan Wang. 2015. An Overview of Microsoft Academic Service (MAS) and Applications. In Proceedings of the 24th International Conference on World Wide Web. ACM Press. https://doi.org/10.1145/2740908.2742839

Digital Library

[18]

Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 1539–1554.

Digital Library

[19]

Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 75–86.

Digital Library

[20]

Prateek Yadav and Arun Rajkumar. 2021. Rank Refinement: An Algorithmic framework with applications to diversity aware influence maximization. https://prateek-yadav.github.io/publications/

[21]

Jianming Zhu, Junlei Zhu, Smita Ghosh, Weili Wu, and Jing Yuan. 2018. Social influence maximization in hypergraph in social networks. IEEE Transactions on Network Science and Engineering 6, 4(2018), 801–811.

Cited By

Gong XWang HWang XChen CZhang WZhang Y(2024)Influence maximization on hypergraphs via multi-hop influence estimationInformation Processing & Management10.1016/j.ipm.2024.10368361:3(103683)Online publication date: May-2024
https://doi.org/10.1016/j.ipm.2024.103683
Xie MZhan XLiu CZhang Z(2023)An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphsInformation Processing and Management: an International Journal10.1016/j.ipm.2022.10316160:2Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103161
Aktas MJawaid SGokalp IAkbas E(2022)Influence Maximization on Hypergraphs via Similarity-based Diffusion2022 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW58026.2022.00158(1197-1206)Online publication date: Nov-2022
https://doi.org/10.1109/ICDMW58026.2022.00158

Index Terms

Hyper-IMRANK: Ranking-based Influence Maximization for Hypergraphs

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

Recommendations

Efficient influence maximization in social networks
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is ...
IMRank: influence maximization via finding self-consistent ranking
SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

Influence maximization, fundamental for word-of-mouth marketing and viral marketing, aims to find a set of seed nodes maximizing influence spread on social network. Early methods mainly fall into two paradigms with certain benefits and drawbacks: (1) ...
Influence maximization on hypergraphs via multi-hop influence estimation
Abstract
Influence Maximization (IM) has promising applications in social network marketing and has been extensively researched over the past years. However, previous IM studies mainly focus on ordinary graphs rather than hypergraphs, where edges cannot ...
Highlights
- We proposed a probability distribution based method MIE to solve the HyperIM problem.
- We proposed an efficient neighbourhood coefficient based method Adeff.
- We conducted extensive experiments to demonstrate the superiority of our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODS-COMAD '22: Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD)

January 2022

357 pages

ISBN:9781450385824

DOI:10.1145/3493700

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 January 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper
Research
Refereed limited

Conference

CODS-COMAD 2022

Sponsor:

SIGGRAPH

CODS-COMAD 2022: 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD)

January 8 - 10, 2022

Bangalore, India

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gong XWang HWang XChen CZhang WZhang Y(2024)Influence maximization on hypergraphs via multi-hop influence estimationInformation Processing & Management10.1016/j.ipm.2024.10368361:3(103683)Online publication date: May-2024
https://doi.org/10.1016/j.ipm.2024.103683
Xie MZhan XLiu CZhang Z(2023)An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphsInformation Processing and Management: an International Journal10.1016/j.ipm.2022.10316160:2Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103161
Aktas MJawaid SGokalp IAkbas E(2022)Influence Maximization on Hypergraphs via Similarity-based Diffusion2022 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW58026.2022.00158(1197-1206)Online publication date: Nov-2022
https://doi.org/10.1109/ICDMW58026.2022.00158

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents