Fair Link Prediction with Multi-Armed Bandit Algorithms
Pages 219 - 228
Abstract
Recommendation systems have been used in many domains, and in recent years, ethical problems associated with such systems have gained serious attention. The problem of unfairness in friendship or link recommendation systems in social networks has begun attracting attention, as such unfairness can cause problems like segmentation and echo chambers. One challenge in this problem is that there are many fairness metrics for networks, and existing methods only consider the improvement of a single specific fairness indicator [16, 17, 20].
In this work, we model the fair link prediction problem as a multi-armed bandit problem. We propose FairLink, a multi-armed bandit based framework that predicts new edges that are both accurate and well-behaved with respect to a fairness property of choice. This method allows the user to specify the desired fairness metric. Experiments on five real-world datasets show that FairLink can achieve a significant fairness improvement as compared to a standard recommendation algorithm, with only a small reduction in accuracy.
References
[1]
[1] Lada A Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery. 36–43.
[2]
[2] Gediminas Adomavicius and YoungOk Kwon. 2012. Improving aggregate recommendation diversity using ranking-based techniques. IEEE Transactions on Knowledge and Data Engineering 24, 5 (2012), 896–911.
[3]
[3] Luca Maria Aiello and Nicola Barbieri. 2017. Evolution of ego-networks in social media with link recommendations. In WSDM. ACM, 111–120.
[4]
[4] Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. 2006. Link prediction using supervised learning. In SDM06: workshop on link analysis, counter-terrorism and security, Vol. 30. 798–805.
[5]
[5] Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, and Yvonne-Anne Pignolet. 2015. Homophily and the glass ceiling effect in social networks. In ITCS. 41–50.
[6]
[6] Robin Burke, Nasim Sonboli, and Aldo Ordonez-Gauger. 2018. Balanced Neighborhoods for Multi-sided Fairness in Recommendation. In FAT*.
[7]
[7] Allison JB Chaney, Brandon M Stewart, and Barbara E Engelhardt. 2017. How Algorithmic Confounding in Recommendation Systems Increases Homogeneity and Decreases Utility. arXiv preprint arXiv:1710.11214 (2017).
[8]
[8] Hsinchun Chen, Xin Li, and Zan Huang. 2005. Link prediction approach to collaborative filtering. In JCDL. IEEE, 141–142.
[9]
[9] SA Curiskis, TR Osborn, and PJ Kennedy. 2015. Link prediction and topological feature importance in social networks. In Australasian Data Mining Conf., Australian Comp. Soc. Inc. 39–50.
[10]
[10] Elizabeth M Daly, Werner Geyer, and David R Millen. 2010. The network effects of recommending social connections. In Proceedings of the fourth ACM conference on Recommender systems. ACM, 301–304.
[11]
[11] Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018. Political discourse on social media: Echo chambers, gatekeepers, and the Price of bipartisanship. arXiv preprint arXiv:1801.01665 (2018).
[12]
[12] Anatoliy Gruzd, Kathleen Staves, and Amanda Wilk. 2011. Tenure and promotion in the age of online social media. Proceedings of the American Society for Information Science and Technology 48, 1 (2011), 1–9.
[13]
[13] Jindong Gu and Daniela Oelke. 2019. Understanding Bias in Machine Learning. arXiv:1909.01866 (2019).
[14]
[14] Zeinab S Jalali, Weixiang Wang, Myunghwan Kim, Hema Raghavan, and Sucheta Soundarajan. 2020. On the Information Unfairness of Social Networks. In SDM.
[15]
[15] Volodymyr Kuleshov and Doina Precup. 2014. Algorithms for multi-armed bandit problems. arXiv preprint arXiv:1402.6028 (2014).
[16]
[16] Charlotte Laclau, Ievgen Redko, Manvi Choudhary, and Christine Largeron. 2021. All of the fairness for edge prediction with optimal transport. In International Conference on Artificial Intelligence and Statistics. PMLR, 1774–1782.
[17]
[17] Yanying Li, Xiuling Wang, Yue Ning, and Hui Wang. 2022. FairLP: Towards Fair Link Prediction on Social Network Graphs. In Proceedings of the International AAAI Conference on Web and Social Media, Vol. 16. 628–639.
[18]
[18] David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. Journal of the American society for information science and technology 58, 7 (2007), 1019–1031.
[19]
[19] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. 2017. A survey of link prediction in complex networks. ACM Computing Surveys (CSUR) 49, 4 (2017), 69.
[20]
[20] Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian. 2020. Bursting the filter bubble: Fairness-aware network link prediction. In AAAI, Vol. 34. 841–848.
[21]
[21] Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415–444.
[22]
[22] Mark EJ Newman. 2006. Modularity and community structure in networks. Proceedings of the national academy of sciences 103, 23 (2006), 8577–8582.
[23]
[23] Javier Sanz-Cruzado, Sofía M Pepa, and Pablo Castells. 2018. Structural Novelty and Diversity in Link Prediction. In WWW. 1347–1351.
[24]
[24] Ana-Andreea Stoica, Christopher Riederer, and Augustin Chaintreau. 2018. Algorithmic Glass Ceiling in Social Networks: The effects of social recommendations on network diversity. In WWW. 923–932.
[25]
[25] Jessica Su, Aneesh Sharma, and Sharad Goel. 2016. The effect of recommendations on network structure. In WWW. 1157–1167.
[26]
[26] Lionel Tabourier, Anne-Sophie Libert, and Renaud Lambiotte. [n.d.]. Predicting links in ego-networks using temporal information. EPJ Data Science 5, 1 ([n. d.]).
[27]
[27] Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, Vol. 1.
[28]
[28] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: extraction and mining of academic social networks. In KDD. 990–998.
[29]
[29] Amanda L Traud, Peter J Mucha, and Mason A Porter. 2012. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications 391, 16 (2012), 4165–4180.
[30]
[30] Joannes Vermorel and Mehryar Mohri. 2005. Multi-armed bandit algorithms and empirical evaluation. In European conference on machine learning. Springer, 437–448.
[31]
[31] Sarita Yardi and Danah Boyd. 2010. Dynamic debates: An analysis of group polarization over time on twitter. Bulletin of science, technology & society 30, 5 (2010), 316–327.
Index Terms
- Fair Link Prediction with Multi-Armed Bandit Algorithms
Recommendations
Wireless packet fair queueing algorithms with link level retransmission
In order to provide quality of service to wireless networks, a number of wireless fair queueing algorithms have recently been proposed. They, however, require perfect channel prediction before transmission and rarely consider algorithms under the link ...
Relay-volunteered multi-rate cooperative MAC protocol for IEEE 802.11 WLANs
In IEEE 802.11, the rate of a station (STA) is dynamically determined by link adaptation. Low-rate STAs tend to hog more channel time than high-rate STAs due to fair characteristics of carrier sense multiple access/collision avoidance, leading to ...
A Two Step Multi-Carrier Proportional Fair Scheduling Scheme for Cloud Radio Access Networks
Proportional fair scheduling PFS is a widely used scheduling algorithm in the wireless networks which utilizes the network resources efficiently while maintaining a balance with the fairness among the users. It is a channel aware scheduling algorithm ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2023
373 pages
ISBN:9798400700897
DOI:10.1145/3578503
- General Chairs:
- Ágnes Horvát,
- Wendy Hall,
- Noshir Contractor,
- Organizing Chair:
- Leon Fröhling,
- Program Chairs:
- Katherine Ognayova,
- Harsh Taneja,
- Ingmar Weber,
- Publications Chairs:
- Kristina Gligori?,
- Yelena Mejova
Copyright © 2023 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 April 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- NSF
Conference
WebSci '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 245 of 933 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 135Total Downloads
- Downloads (Last 12 months)78
- Downloads (Last 6 weeks)2
Reflects downloads up to 19 Nov 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 inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format