Social Networks 1
Wednesday, 2:00-3:00 PM
Chair: Alex Ntoulas
Predicting Positive and Negative Links in Online Social Networks
Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg
We study online social networks in which relationships can be both positive (indicating friendship) and negative (indicating opposition or antagonism). Such a mix of positive and negative links arise in a variety of online settings; we study datasets from Epinions, Slashdot and Wikipedia. Despite the diversity of settings considered, we find that the signs of links in the underlying social networks can be predicted with high accuracy using models that generalize across the different domains. These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, and also shed light on theories of balance and status from social psychology.
Empirical Comparison of Algorithms for Network Community Detection
Jure Leskovec, Kevin Lang, Michael Mahoney
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that “look like” good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases of clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
Modeling Relationship Strength in Online Social Network
Rongjing Xiang, Jennifer Neville, Monica Rogati
Previous work analyzing social networks has mainly focused on binary friendship relations. However, in online social networks the low cost of link formation can lead to networks with heterogeneous relationship strengths (e.g., acquaintances and best friends mixed together). In this case, the binary friendship indicator provides only a coarse representation of relationship information. In this work, we develop an unsupervised model to estimate relationship strength from interaction activity (e.g., communication, tagging) and user similarity. More specifically, we formulate a link-based latent variable model, along with a coordinate ascent optimization procedure for the inference. We evaluate our approach on real-world data from Facebook and LinkedIn, showing that the estimated link weights result in higher autocorrelation and lead to improved classification accuracy.
.
