Acknowledgment: This material is based upon work supported by the National Science Foundation under Grant No. 1619458
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Award Number: 1619458
Award Title: III: Small: Robustness in Social Network Analysis: Models, Inference, and Algorithms
Social networks - online and offline - play a large role in people's daily lives. In return, they implicitly contain a large amount of information about individuals and their traits and preferences. The burgeoning field of "Social Network Analysis" focuses on extracting useful insights from such social network data. Implemented or envisioned applications range from learning about the nature and driving forces behind human interactions, to targeted product or activity recommendations and even homeland security. Contrary to other networks, such as transportation or computer networks, massive uncertainty and noise are practically always associated with social network data: data pertaining to individuals are often not observable, or are observed incorrectly. The primary goal of this project is to understand the risks and implications of such noisy data, and to design network analysis algorithms that are significantly more robust to noise and missing data. Given the importance that mathematical models play in social networks analysis, a closely related thread of the project is to analyze the fit between typical social network models and real-world data, in particular regarding high-level connectivity properties. Specifically, three connected research thrusts are being explored:
The proposed research has the potential to impact the way in which social network inference and optimization are addressed. The PIs are committed to a suite of activities, among them inclusion of undergraduate students in the proposed research and outreach to local high school students, for broader impacts.
Karishma Sharma, Xinran He, Sungyong Seo, Yan Liu: Network Inference from a Mixture of Diffusion Models for Fake News Mitigation. In Proc. of 15th International AAAI Conference on Web and Social Media, ICWSM, 2021. Full version on arXiv.
Ehsan Emamjomeh-Zadeh, Yannai A. Gonczarowki, David Kempe: The Complexity of Interactively Learning a Stable Matching by Trial and Error. In Proc. of EC 2020. Full version on arXiv.
Ehsan Emamjomeh-Zadeh, David Kempe, Mohammad Mahdian, Rob Schapire: Interactive Learning of a Dynamic Structure. In Proc. of Intl. Conf. on Algorithmic Learning Theory 2020, San Diego, CA. Full version in PDF.
Karishma Sharma, Chuizheng Meng, Sungyong Seo, Sirisha Rambhatla, Yan Liu: Covid-19 on Social Media: Analyzing Misinformation in Twitter Conversations. Journal of Computational Social Science, Special Issue on Misinformation, Manipulation and Abuse on Social Media in the Era of COVID-19, 2020. Full version on arXiv.
Karishma Sharma, Feng Qian, He Jiang, Natali Ruchansky, Ming Zhang, Yan Liu.
Combating Fake News: A Survey on Identification and Mitigation Techniques.
ACM Transactions on Intelligent Systems and Technology (TIST)
Vol. 10/3, Article 21, 2019
Full version on arXiv.
Kartik Lakhotia, David Kempe: Approximation Algorithms for Coordinating Ad Campaigns on Social Networks. In Proc. of 2019 ACM Intl. Conf. on Information and Knowledge Management, Beijing, China. Full version on arXiv.
Alana Shine, David Kempe. Generative Graph Models based on Laplacian Spectra. In Proc. of The Web Conference (WWW) 2019, San Francisco, CA. Link to conference version.
Xinran He, David Kempe.
Stability and Robustness in Influence Maximization.
ACM Transactions on Knowledge Discovery from Data (TKDD),
Vol. 18/6, 10/2018, Article 66.
Full version in PDF.
Feng Qian, Chengyue Gong, Karishma Sharma, Yan Liu. Neural User Response Generator: Fake News Detection with Collective User Intelligence. In Proc. of IJCAI 2018, Stockholm, Sweden. Link to conference version and data set.
Ehsan Emamjomeh-Zadeh, David Kempe. Adaptive Hierarchical Clustering Using Ordinal Queries. In Proc. of SODA 2018, New Orleans, LA. Full version on arXiv.
Ehsan Emamjomeh-Zadeh, David Kempe. A General Framework for Robust Interactive Learning. In Proc. of NIPS 2017, Long Beach, CA. Full version on arXiv.
Sungyong Seo, Natali Ruchansky, Yan Liu. CSI: A Hybrid Deep Model for Fake News Detection. In Proc. of CIKM 2017. Full version on arXiv.
Palash Goyal, Nitin Kamra, Xinran He, Yan Liu. DynGEM: Deep Embedding Method for Dynamic Graphs. To appear in 3rd Representation Learning for Graphs Workshop (ReLiG 2017) with IJCAI'17.
Xinran He, Yan Liu. Not Enough Data? Joint Inferring Multiple Diffusion Networks via Network Generation Priors. In Proc. of WSDM 2017. Link to paper.
Xinran He, Ke Xu, David Kempe, Yan Liu. Learning Influence Functions from Incomplete Observations. In Proc. of NIPS 2016, Barcelona, Spain. Full version on arXiv.
Xinran He, David Kempe. Robust Influence Maximization. In Proc. of KDD 2016, San Francisco, CA. Full version on arXiv.
All software and data for the project on generating random graphs subject to spectrum constraints is available on Alana Shine's Github page.
The code for running influence maximization algorithms under uncertainty is available on Xinran He's Github page.
The data set for the IJCAI 2018 paper on misinformation.
The data set on Covid-19 misinformation.
Our work has resulted in a publicly accessible Dashboard on Covid-19 misinformation campaigns.