Learning to predict reciprocity and triadic closure in social networks
ACM Transactions on Knowledge Discovery from DataPublished 1 July 2013
Tiancheng Lou, Jie Tang, John E. Hopcroft, Zhanpeng Fang, Xiaowen Ding
Citations105
SJR quartileQ1
SJR score1.19
SNIP1.91
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is demonstrated that it is possible to accurately infer 90% of reciprocal relationships in a Twitter network, and a learning framework is proposed to formulate the problems of predicting reciprocity and triadic closure into a graphical model.
Abstract
We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships further develop into triadic closure, one of the fundamental processes of link formation. We first investigate how geographic distance and interactions between users influence the formation of link structure among users. Then we study how social theories including homophily, social balance, and social status are satisfied over networks with parasocial and reciprocal relationships. The study unveils several interesting phenomena. For example, “friend's friend is a friend” indeed exists in the reciprocal relationship network, but does not hold in the parasocial relationship network. We propose a learning framework to formulate the problems of predicting reciprocity and triadic closure into a graphical model. We demonstrate that it is possible to accurately infer 90% of reciprocal relationships in a Twitter network. The proposed model also achieves better performance (+20--30% in terms of F1-measure) than several alternative methods for predicting the triadic closure formation.
Keywords
Computer SciencePhysics and Astronomy
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
What is Twitter, a social network or a news media?
6,692 Citations2010Haewoon Kwak, Changhyun Lee +2 more
This work is the first quantitative study on the entire Twittersphere and information diffusion on it and finds a non-power-law follower distribution, a short effective diameter, and low reciprocity, which all mark a deviation from known characteristics of human social networks.
PsychiatryMass Communication and Para-Social Interaction
3,997 Citations1956Donald Horton, Robert Wohl
PsychometrikaA New Status Index Derived from Sociometric Analysis
3,863 Citations1953Leo Katz
A new method of computation which takes into account who chooses as well as how many choose is presented, which introduces the concept of attenuation in influence transmitted through intermediaries.
Earthquake shakes Twitter users
3,667 Citations2010Takeshi Sakaki, Makoto Okazaki +1 more
This paper investigates the real-time interaction of events such as earthquakes in Twitter and proposes an algorithm to monitor tweets and to detect a target event and produces a probabilistic spatiotemporal model for the target event that can find the center and the trajectory of the event location.
Proceedings of the International AAAI Conference on Web and Social MediaMeasuring User Influence in Twitter: The Million Follower Fallacy
3,009 Citations2010Meeyoung Cha, Hamed Haddadi +2 more
An in-depth comparison of three measures of influence, using a large amount of data collected from Twitter, is presented, suggesting that topological measures such as indegree alone reveals very little about the influence of a user.
Networks, crowds, and markets reasoning about a highly connected world
2,749 CitationsDavid Easley, Jon Kleinberg
This introductory book on the new science of networks takes an interdisciplinary approach, using economics, sociology, computing, information science and applied mathematics to address fundamental questions about the links that connect us, and the ways that the authors' decisions can have consequences for others.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsClustering and preferential attachment in growing networks
2,047 Citations2001M. E. J. Newman
It is shown that the probability of a pair of scientists collaborating increases with the number of other collaborators they have in common, and that the probabilities of a particular scientist acquiring new collaborators increases withThe number of his or her past collaborators.
Proceedings of the National Academy of SciencesInferring friendship network structure by using mobile phone data
1,886 Citations2009Nathan Eagle, Alex Pentland +1 more
It is demonstrated that it is possible to accurately infer 95% of friendships based on the observational data alone, where friend dyads demonstrate distinctive temporal and spatial patterns in their physical proximity and calling patterns that allow the prediction of individual-level outcomes such as job satisfaction.
TwitterRank
1,734 Citations2010Jianshu Weng, Ee‐Peng Lim +2 more
Experimental results show that TwitterRank outperforms the one Twitter currently uses and other related algorithms, including the original PageRank and Topic-sensitive PageRank, which is proposed to measure the influence of users in Twitter.
arXiv (Cornell University)Loopy Belief Propagation for Approximate Inference: An Empirical Study
1,468 Citations2013Kevin P. Murphy, Yair Weiss +1 more
Predicting positive and negative links in online social networks
1,454 Citations2010Jure Leskovec, Daniel P. Huttenlocher +1 more
These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology and suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
Supervised random walks
996 Citations2011Lars Bäckström, Jure Leskovec
An algorithm based on Supervised Random Walks is developed that naturally combines the information from the network structure with node and edge level attributes and outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction.
Who says what to whom on twitter
952 Citations2011Shaomei Wu, Jake M. Hofman +2 more
A striking concentration of attention is found on Twitter, in that roughly 50% of URLs consumed are generated by just 20K elite users, where the media produces the most information, but celebrities are the most followed.
Social influence analysis in large-scale networks
909 Citations2009Jie Tang, Jimeng Sun +2 more
Topical Affinity Propagation (TAP) is designed with efficient distributed learning algorithms that is implemented and tested under the Map-Reduce framework and can take results of any topic modeling and the existing network structure to perform topic-level influence propagation.
TwitterMonitor
818 Citations2010Michael Mathioudakis, Nick Koudas
TwitterMonitor, a system that performs trend detection over the Twitter stream and provides meaningful analytics that synthesize an accurate description of each topic on Twitter in real time, is presented.
New perspectives and methods in link prediction
673 Citations2010Ryan N. Lichtenwalter, Jake T. Lussier +1 more
This paper examines important factors for link prediction in networks and provides a general, high-performance framework for the prediction task and presents an effective flow-based predicting algorithm, formal bounds on imbalance in sparse network link prediction, and employ an evaluation method appropriate for the observed imbalance.
SSRN Electronic JournalSocial Networks that Matter: Twitter Under the Microscope
520 Citations2008Bernardo A. Huberman, Daniel M. Romero +1 more
A study of social interactions within Twitter reveals that the driver of usage is a sparse and hidden network of connections underlying the “declared” set of friends and followers.
Proceedings of the National Academy of SciencesInferring social ties from geographic coincidences
481 Citations2010David Crandall, Lars Bäckström +4 more
A framework for quantifying the answers to questions about social ties between people is developed, and this framework is applied to publicly available data from a social media site, finding that even a very small number of co-occurrences can result in a high empirical likelihood of a social tie.
User-level sentiment analysis incorporating social networks
400 Citations2011Chenhao Tan, Lillian Lee +4 more
It is shown that information about social relationships can be used to improve user-level sentiment analysis and incorporating social-network information can indeed lead to statistically significant sentiment classification improvements over the performance of an approach based on Support Vector Machines having access only to textual features.
Local Probabilistic Models for Link Prediction
322 Citations2007Chao Wang, Venu Satuluri +1 more
A novel local probabilistic graphical model method that can scale to large graphs to estimate the joint co-occurrence probability of two nodes and is demonstrated to be effective both in isolation and in combination with other topological and semantic features for predicting co-authorship collaborations on real datasets.
Inferring social ties across heterogenous networks
300 Citations2012Jie Tang, Tiancheng Lou +1 more
The framework incorporates social theories into a factor graph model, which effectively improves the accuracy of inferring the type of social relationships in a target network by borrowing knowledge from a different source network.
Cross-domain collaboration recommendation
293 Citations2012Jie Tang, Sen Wu +2 more
The Cross-domain Topic Learning (CTL) model is proposed, which consolidates the existing cross-domain collaborations through topic layers instead of at author layers, which alleviates the sparseness issue and outperforms baselines significantly on multiple recommendation metrics.
Understanding retweeting behaviors in social networks
250 Citations2010Zi Yang, Jingyi Guo +5 more
This paper proposes a factor graph model to predict users' retweeting behaviors and shows that this method can achieve a precision of 28.81% and recall of 37.33% for prediction of the retweet behaviors.
Lecture notes in computer scienceWhy We Twitter: An Analysis of a Microblogging Community
233 Citations2009Akshay Java, Xiaodan Song +2 more
It is found that people use microblogging primarily to talk about their daily activities and to seek or share information and that users with similar intentions connect with each other.
Mining advisor-advisee relationships from research publication networks
203 Citations2010Chi Wang, Jiawei Han +5 more
A time-constrained probabilistic factor graph model (TPFG), which takes a research publication network as input and models the advisor-advisee relationship mining problem using a jointly likelihood objective function is proposed and an efficient learning algorithm is designed to optimize the objective function.
Who will follow you back?
167 Citations2011John E. Hopcroft, Tiancheng Lou +1 more
This study provides strong evidence of the existence of the structural balance among reciprocal relationships and proposes a learning framework to formulate the problem of reciprocal relationship prediction into a graphical model that incorporates social theories into a machine learning model.
Graph-based ranking algorithms for e-mail expertise analysis
158 Citations2003Byron Dom, Iris Eiron +2 more
This paper focuses on the analysis of digraphs whose nodes correspond to correspondents (people), whose edges correspond to the existence of email correspondence between the people corresponding to the nodes they connect and whose edge directions point from the member of the pair whose relative expertise has been estimated to be higher.
arXiv (Cornell University)A Generalized Mean Field Algorithm for Variational Inference in\n Exponential Families
150 Citations2012Eric P. Xing, Michael I. Jordan +1 more
Lecture notes in computer scienceLearning to Infer Social Ties in Large Networks
144 Citations2011Wenbin Tang, Honglei Zhuang +1 more
This work formalizes the problem of social relationship learning into a semi-supervised framework, and proposes a Partially-labeled Pairwise Factor Graph Model (PLP-FGM) for learning to infer the type of social ties.
Relationship identification for social network discovery
97 Citations2007Christopher Diehl, Galileo Namata +1 more
A supervised ranking approach is proposed to the challenge of relationship identification where the objective is to identify relevant communications that substantiate a given social relationship type and its performance on a manager-subordinate relationship identification task using the Enron email corpus is assessed.
Preferential behavior in online groups
93 Citations2008Lars Bäckström, Ravi Kumar +3 more
It is shown that users who will go on to become long-lived, highly-engaged users experience significantly better treatment than other users from the moment they join the group, well before there is an opportunity for them to develop a long-standing relationship with members of the group.
Social action tracking via noise tolerant time-varying factor graphs
88 Citations2010Chenhao Tan, Jie Tang +3 more
Experimental results show that the proposed method outperforms several baseline methods for action prediction, and Qualitatively, the model can uncover some interesting patterns of the social dynamics.
arXiv (Cornell University)The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter
52 Citations2010Daniel M. Romero, Jon Kleinberg
Data Mining and Knowledge DiscoveryActively learning to infer social ties
33 Citations2012Honglei Zhuang, Jie Tang +4 more
This work precisely defines the problem of inferring social ties and proposes a Partially-Labeled Pairwise Factor Graph Model (PLP-FGM) for learning to infer the type of social relationships and formalizes the problem into a flexible semi-supervised framework.
Lecture notes in computer scienceDetecting the Structure of Social Networks Using (α,β)-Communities
16 Citations2011Jing He, John E. Hopcroft +3 more
This paper presents a heuristic ( α, β)-Community algorithm, which in practice successfully finds (α,β)-communities of a given size, and demonstrates that the core structure displayed in various social graphs is due to the underlying social structure of these real-world networks, rather than due to high-degree vertices or a particular degree distribution.