Fair Influence Maximization in Hypergraphs
Pages 8 - 14
Abstract
Influence maximization (IM) traditionally prioritizes maximizing influence spread, often resulting in challenges such as unfair information dissemination and social bias. To mitigate these issues, the fair influence maximization (FIM) has been introduced, focusing on minimizing the influence gap between different groups while still maximizing influence spread. However, existing FIM approaches predominantly target simple networks, neglecting the higher-order relationships that are prevalent in real-world systems. In this paper, we extend the FIM problem to hypergraphs and propose the Local Attribute and Higher-order Degree-based (LAHD) method. LAHD addresses FIM by evaluating node fairness through the local attribute distribution of neighboring nodes and node influence through higher-order degree metrics. Experimental results on both real-world and synthetic hypergraphs demonstrate that LAHD outperforms baseline methods in achieving both fairness and influence spread.
References
[1]
Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, pages 61--70, New York, NY, USA, 2002. ACM.
[2]
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '07, pages 420--429, New York, NY, USA, 2007. ACM.
[3]
Amit Goyal, Wei Lu, and Laks V.S. Lakshmanan. Celf+ +: optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web, WWW '11, pages 47--48, New York, NY, USA, 2011. ACM.
[4]
Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, pages 199--208, New York, NY, USA, 2009. ACM.
[5]
Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. Influence maximization over large-scale social networks: A bounded linear approach. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM '14, pages 171--180, New York, NY, USA, 2014. ACM.
[6]
Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 946--957, Philadelphia, PA, 2014. Society for Industrial and Applied Mathematics.
[7]
Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD '18, pages 991--1005, New York, NY, USA, 2018. ACM.
[8]
Yasir Mehmood, Francesco Bonchi, and David García-Soriano. Spheres of influence for more effective viral marketing. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, page 711--726, New York, NY, USA, 2016. ACM.
[9]
Xinran He, Guojie Song, Wei Chen, and Qingye Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In Proceedings of the 2012 SIAM International Conference on Data Mining (SDM), pages 463--474, Philadelphia, PA, 2012. Society for Industrial and Applied Mathematics.
[10]
Amulya Yadav, Bryan Wilder, Eric Rice, Robin Petering, Jaih Craddock, Amanda Yoshioka-Maxwell, Mary Hemler, Laura Onasch-Vera, Milind Tambe, and Darlene Woo. Bridging the gap between theory and practice in influence maximization: raising awareness about hiv among homeless youth. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI'18, pages 5399--5403, Stockholm Sweden, 2018. AAAI Press.
[11]
David Kempe, Jon Kleinberg, and Éva 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, KDD '03, page 137--146, New York, NY, USA, 2003. ACM.
[12]
Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairness in influence maximization. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), pages 5997--6005, August 2019.
[13]
Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju, Phebe Vayanos, Max Izenberg, Ryan Brown, Eric Rice, and Milind Tambe. Fair influence maximization: a welfare optimization approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11630--11638, Palo Alto, California USA, 2021. AAAI Press.
[14]
Yuting Feng, Ankitkumar Patel, Bogdan Cautis, and Hossein Vahabi. Influence maximization with fairness at scale. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pages 4046--4055, New York, NY, USA, 2023. ACM.
[15]
Mingkai Lin, Lintan Sun, Rui Yang, Xusheng Liu, Yajuan Wang, Ding Li, Wenzhong Li, and Sanglu Lu. Fair influence maximization in large-scale social networks based on attribute-aware reverse influence sampling. Journal of Artificial Intelligence Research, 76:925--957, April 2023.
[16]
Xiaobin Rui, Zhixiao Wang, Jiayu Zhao, Lichao Sun, and Wei Chen. Scalable fair influence maximization. Advances in Neural Information Processing Systems, 36:66675--66691, 2023.
[17]
Kaicong Ma, Xinxiang Xu, Haipeng Yang, Renzhi Cao, and Lei Zhang. Fair influence maximization in social networks: A community-based evolutionary algorithm. IEEE Transactions on Emerging Topics in Computing, pages 1--13, May 2024.
[18]
Ruben Becker, Gianlorenzo D'angelo, Sajjad Ghobadi, and Hugo Gilbert. Fairness in influence maximization through randomization. Journal of Artificial Intelligence Research, 73:1251--1283, April 2022.
[19]
Moein Khajehnejad, Ahmad Asgharian Rezaei, Mahmoudreza Babaei, Jessica Hoffmann, Mahdi Jalili, and Adrian Weller. Adversarial graph embeddings for fair influence maximization over social networks. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, volume 594 of IJCAI'20, pages 4306--4312, Yokohama, Japan, 2021. ACM.
[20]
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 214--226, New York, NY, USA, 2012. ACM.
[21]
Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. Gaps in information access in social networks? In The World Wide Web Conference, WWW '19, pages 480--490, New York, NY, USA, 2019. ACM.
[22]
Golnoosh Farnad, Behrouz Babaki, and Michel Gendreau. A unifying framework for fairness-aware influence maximization. In Companion Proceedings of the Web Conference 2020, WWW '20, pages 714--722, New York, NY, USA, 2020. ACM.
[23]
Ernesto Estrada and Juan A Rodríguez-Velázquez. Subgraph centrality and clustering in complex hyper-networks. Physica A: Statistical Mechanics and its Applications, 364:581--594, August 2006.
[24]
Ning Ma and Yijun Liu. Superedgerank algorithm and its application in identifying opinion leader of online public opinion supernetwork. Expert Systems with Applications, 41(4):1357--1368, March 2014.
[25]
Flora Amato, Vincenzo Moscato, Antonio Picariello, and Giancarlo Sperlí. Influence maximization in social media networks using hypergraphs. In Green, Pervasive, and Cloud Computing, pages 207--221, Cham, 2017. Springer International Publishing.
[26]
Athul MA and Arun Rajkumar. Hyper-imrank: Ranking-based influence maximization for hypergraphs. In Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD), CODS-COMAD '22, pages 100--104, New York, NY, USA, 2022. ACM.
[27]
Ming Xie, Xiu-Xiu Zhan, Chuang Liu, and Zi-Ke Zhang. An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs. Information Processing& Management, 60(2):103161, March 2023.
[28]
Linyuan Lü, Duanbing Chen, Xiao-Long Ren, Qian-Ming Zhang, Yi-Cheng Zhang, and Tao Zhou. Vital nodes identification in complex networks. Physics Reports, 650:1--63, September 2016. Vital nodes identification in complex networks.
[29]
Clara Stegehuis and Thomas Peron. Network processes on clique-networks with high average degree: the limited effect of higher-order structure. Journal of Physics: Complexity, 2(4):045011, November 2021.
[30]
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2):cnab014, May 2021.
[31]
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: an automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DL '98, page 89--98, New York, NY, USA, 1998. Association for Computing Machinery.
[32]
Yandi Li, Haobo Gao, Yunxuan Gao, Jianxiong Guo, and Weili Wu. A survey on influence maximization: From an ml-based combinatorial optimization. ACM Trans. Knowl. Discov. Data, 17(9), July 2023.
[33]
Sanjay Kumar, Abhishek Mallik, Anavi Khetarpal, and B.S. Panda. Influence maximization in social networks using graph embedding and graph neural network. Information Sciences, 607:1617--1636, August 2022.
Index Terms
- Fair Influence Maximization in Hypergraphs
Recommendations
Covering Non-uniform Hypergraphs
A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...
Odd cycles and Θ-cycles in hypergraphs
A @Q-cycle of a hypergraph is a cycle including an edge that contains at least three base points of the cycle. We show that if a hypergraph H=(V,E) has no @Q-cycle, and |e|>=3, for every edge e@__ __E, then @__ __"e"@__ __"E(|e|-1)=<2|V|-2 with equality ...
Maximally edge-connected hypergraphs
The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2024
65 pages
ISBN:9798400712999
DOI:10.1145/3698387
Copyright © 2024 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
- SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
- SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
- SIGOPS: ACM Special Interest Group on Operating Systems
- SIGBED: ACM Special Interest Group on Embedded Systems
- SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 November 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- the Natural Science Foundation of Zhejiang Province
- the Natural Science Foundation of China
- Scientific Research Foundation for Scholars of HZNU
Conference
SenSys '24
SenSys '24: The 22nd ACM Conference on Embedded Networked Sensor Systems
November 4 - 7, 2024
Hangzhou, China
Acceptance Rates
SocialMeta '24 Paper Acceptance Rate 9 of 11 submissions, 82%;
Overall Acceptance Rate 9 of 11 submissions, 82%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 41Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)29
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in