NETEVOLVE: Social Network Forecasting using Multi-Agent Reinforcement Learning with Interpretable Features
Authors: 
Kentaro Miyake, Hiroyoshi Ito, 
Christos Faloutsos, Hirotomo Matsumoto, Atsuyuki MorishimaAuthors Info & Claims
Kentaro Miyake, Hiroyoshi Ito, Christos Faloutsos, Hirotomo Matsumoto, Atsuyuki MorishimaAuthors Info & ClaimsPages 2542 - 2551
Abstract
Predicting how social networks change in the future is important in many applications. Results in social network research have shown that the change in the network can be explained by a small number of concepts, such as "homophily" and "transitivity". However, existing prediction methods require many latent features that are not connected to such concepts, making the methods' black boxes and their prediction results difficult to interpret, making them harder to derive scientific knowledge about social networks. In this study, we propose NetEvolve a novel multi-agent reinforcement learning-based method that predicts changes in a given social network. Given a sequence of changes as training data, NetEvolve learns the characteristics of the nodes with interpretable features, such as how the node feels rewards for connecting with similar people and the cost of the connection itself. Based on the learned feature, NetEvolve makes a forecast based on multi-agent simulation. The method achieves comparable or better accuracy than existing methods in predicting network changes in real-world social networks while keeping the prediction results interpretable.
Supplemental Material
MP4 File
Supplemental video
- Download
- 95.52 MB
References
[1]
Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing. 2008. Mixed membership stochastic blockmodels. In Proceedings of Advances in Neural Information Processing Systems (NIPS'08). 1981--2014.
[2]
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD'19). 2623--2631.
[3]
Gil Appel, Lauren Grewal, Rhonda Hadi, and Andrew T Stephen. 2020. The future of social media in marketing. Journal of the Academy of Marketing science 48, 1 (2020), 79--95.
[4]
Miguel Araújo, Pedro Ribeiro, and Christos Faloutsos. 2018. Tensorcast: forecasting time-evolving networks with contextual information. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI'18). 5199--5203.
[5]
Sitaram Asur and Bernardo A Huberman. 2010. Predicting the future with social media. In Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT'10), Vol. 1. IEEE, 492--499.
[6]
Richard Bellman. 1957. A Markovian decision process. Journal of mathematics and mechanics (1957), 679--684.
[7]
Ayan Kumar Bhowmick. 2019. Lady Gaga dataset. https://doi.org/10.5281/zenodo.2586362
[8]
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017. Enriching word vectors with subword information. Transactions of the association for computational linguistics 5 (2017), 135--146.
[9]
Yann Bramoullé, Sergio Currarini, Matthew O Jackson, Paolo Pin, and Brian W Rogers. 2012. Homophily and long-run integration in social networks. Journal of Economic Theory 147, 5 (2012), 1754--1786.
[10]
Lucian Busoniu, Robert Babuska, and Bart De Schutter. 2008. A Comprehensive Survey of Multiagent Reinforcement Learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 38, 2 (2008), 156--172.
[11]
Huiyuan Chen and Jing Li. 2018. Exploiting structural and temporal evolution in dynamic link prediction. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM'18). 427--436.
[12]
Yang Chen, Jiamou Liu, He Zhao, and Hongyi Su. 2020. Social structure emergence: A multi-agent reinforcement learning framework for relationship building. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS'20). 1807--1809.
[13]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018).
[14]
Nan Du, Christos Faloutsos, Bai Wang, and Leman Akoglu. 2009. Large Human Communication Networks: Patterns and a Utility-Driven Generator. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09). 269--278.
[15]
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. 2020. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based Systems 187 (2020).
[16]
Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'16). 855--864.
[17]
Yupeng Gu, Yizhou Sun, and Jianxi Gao. 2017. The Co-evolution model for social network evolving and opinion migration. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'17). 175--184.
[18]
Shubham Gupta, Gaurav Sharma, and Ambedkar Dukkipati. 2019. A Generative Model for Dynamic Networks with Applications. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'19), Vol. 33. 7842--7849.
[19]
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. 2019. Variational graph recurrent neural networks. Proceedings of Advances in Neural Information Processing Systems (NeurIPS'19) 32 (2019).
[20]
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of Advances in Nneural Information Processing Systems (NIPS'17). 1024--1034.
[21]
Christopher Hare and Keith T Poole. 2014. The polarization of contemporary American politics. Polity 46, 3 (2014), 411--429.
[22]
Creighton Heaukulani and Zoubin Ghahramani. 2013. Dynamic probabilistic models for latent feature propagation in social networks. In Proceedings of International Conference on Machine Learning (ICML'13). 275--283.
[23]
Itai Himelboim, Kaye Sweetser, Spencer Tinkham, Kristen Cameron, Matthew Danelo, and Kate West. 2014. Valence-based homophily on Twitter: Network Analysis of Emotions and Political Talk in the 2012 Presidential Election. New Media & Society 18 (2014), 1382--1400.
[24]
Junling Hu, Michael P Wellman, et al. 1998. Multiagent reinforcement learning: theoretical framework and an algorithm. In International Conference on Machine Learning (ICML'98). 242--250.
[25]
Daniel J. Isenberg. 1986. Group polarization: A critical review and meta-analysis. Journal of Personality and Social Psychology 50 (1986), 1141--1151.
[26]
Hiroyoshi Ito and Christos Faloutsos. 2022. DualCast: Friendship-Preference Co-evolution Forecasting for Attributed Networks. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM'22). 46--54.
[27]
Hiroyoshi Ito, Takahiro Komamizu, Toshiyuki Amagasa, and Hiroyuki Kitagawa. 2018. Network-word embedding for dynamic text attributed networks. In 2018 IEEE 12th International Conference on Semantic Computing (ICSC'18). IEEE, 334--339.
[28]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
[29]
Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016).
[30]
Mirko Lai, Viviana Patti, Giancarlo Ruffo, and Paolo Rosso. 2018. Stance evolution and twitter interactions in an italian political debate. In Proceedings of 23rd International Conference on Applications of Natural Language to Information Systems (NLDB'18). Springer, 15--27.
[31]
Marcus Lim, Azween Abdullah, NZ Jhanjhi, Muhammad Khurram Khan, and Mahadevan Supramaniam. 2019. Link prediction in time-evolving criminal network with deep reinforcement learning technique. IEEE Access 7 (2019), 184797--184807.
[32]
Carlos Lozares, Joan Miquel Verd, Irene Cruz, and Oriol Barranco. 2014. Homophily and heterophily in personal networks. From mutual acquaintance to relationship intensity. Quality & Quantity 48 (2014), 2657--2670.
[33]
Miller Mcpherson, Lynn Smith-Lovin, and James Cook. 2001. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology 27 (2001), 415--444. https://doi.org/10.3410/f.725356294.793504070
[34]
Mingshuo Nie, Dongming Chen, and Dongqi Wang. 2023. Reinforcement learning on graphs: A survey. IEEE Transactions on Emerging Topics in Computational Intelligence (2023).
[35]
Aastha Nigam, Kijung Shin, Ashwin Bahulkar, Bryan Hooi, David Hachen, Boleslaw K Szymanski, Christos Faloutsos, and Nitesh V Chawla. 2018. One-m: Modeling the co-evolution of opinions and network connections. In Proceedings of Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD'18). Springer, 122--140.
[36]
Maya Okawa and Tomoharu Iwata. 2022. Predicting Opinion Dynamics via Sociologically-Informed Neural Networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'22). 1306--1316.
[37]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (KDD'14). 701--710.
[38]
George A. Quattrone and Edward Ellsworth Jones. 1980. The perception of variability within in-groups and out-groups: Implications for the law of small numbers. Journal of Personality and Social Psychology 38 (1980), 141--152.
[39]
Pablo Sánchez-Núñez, Manuel J Cobo, Carlos De las Heras-Pedrosa, Jose Ignacio Pelaez, and Enrique Herrera-Viedma. 2020. Opinion mining, sentiment analysis and emotion understanding in advertising: a bibliometric analysis. IEEE Access 8 (2020), 134563--134576.
[40]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web (WWW'15). 1067--1077.
[41]
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. 2019. Dyrep: Learning representations over dynamic graphs. In Proceedings of International Conference on Learning Representations (ICLR'17).
[42]
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. 2018. Graphgan: Graph representation learning with generative adversarial nets. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'18), Vol. 32.
[43]
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017. Community preserving network embedding. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI'17). 203--209.
[44]
Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. Vol. 8. Cambridge university press.
[45]
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. 2014. Natural evolution strategies. The Journal of Machine Learning Research 15, 1 (2014), 949--980.
[46]
Ronald J. Williams. 1992. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Learning 8, 3--4 (1992), 229--256.
[47]
Lantao Yu, Jiaming Song, and Stefano Ermon. 2019. Multi-Agent Adversarial Inverse Reinforcement Learning. arXiv preprint arxiv:1907.13220 (2019).
[48]
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S. Yu. 2016. Graph Neural Networks for Graphs with Heterophily: A Survey. arXiv preprint arXiv:2202.07082 (2016).
[49]
Le-kui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. 2018. Dynamic Network Embedding by Modeling Triadic Closure Process. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI'18). 571--578.
Index Terms
- NETEVOLVE: Social Network Forecasting using Multi-Agent Reinforcement Learning with Interpretable Features
Recommendations
A multi-agent reinforcement learning approach to robot soccer
In this paper, a multi-agent reinforcement learning method based on action prediction of other agent is proposed. In a multi-agent system, action selection of the learning agent is unavoidably impacted by other agents' actions. Therefore, joint-state ...
Meta Actor-Critic Framework for Multi-Agent Reinforcement Learning
AIPR '21: Proceedings of the 2021 4th International Conference on Artificial Intelligence and Pattern RecognitionIn recent years, multi-agent reinforcement learning has received sustained attention in the last few years. The typical Actor-Critic methods learn mappings directly from observation to action without understanding the tasks themselves. In this paper, we ...
Multi-Agent Inverse Reinforcement Learning
ICMLA '10: Proceedings of the 2010 Ninth International Conference on Machine Learning and ApplicationsLearning the reward function of an agent by observing its behavior is termed inverse reinforcement learning and has applications in learning from demonstration or apprenticeship learning. We introduce the problem of multi-agent inverse reinforcement ...
Comments
Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 399Total Downloads
- Downloads (Last 12 months)399
- Downloads (Last 6 weeks)92
Reflects downloads up to 22 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