DISC 2011
the 25th International Symposium on DIStributed Computing - September 20-22



DISC's SON - 23th September

DISC's Social Network Workshop

When: September 23th

Where: Dipartimento di Ingegneria Informatica e Sistemistica 'A. Ruberti' - Via Ariosto, 25 - Aula Magna

Organizers: Alessandro Panconesi (University of Rome 'La Sapienza' - Dipartimento di Informatica)

Contacts:
Alessandro Panconesi (University of Rome 'La Sapienza')
e-mail: ale@di.uniroma1.it

Computational social science is an emerging discipline at the intersection of computer science, statistics, and the social sciences with the potential of introducing a momentous paradigm shift in sociology and social psychology. In some sense, social networks are distributed systems and it is therefore not surprising that that there is a significant overlap between distributed computing and the study of social networks. In this workshop several well-known researchers in this exciting field will present their work and points of view. We expect the discussion to foster a better understanding of what is currently known and to point to promising new avenues of research and intriguing open problems.

See the program of the workshop here.

Speakers:

Paolo Boldi, Università di Milano
Flavio Chierichetti, Cornell University
Sharad Goel, Yahoo! Research
Pierre Fraigniaud, Université Paris Diderot - Paris 7
Thomas Karagiannis, Microsoft Research
Anne-Marie Kermarrec, Inria
Vahab Mirrokni, Google
Milan Vojnovic, Microsoft Research



Program

Paolo Boldi, Università degli Studi di Milano and Johan Ugander, Cornell University
Social networks and distance distributions


Studying the morphological properties of social networks is important to understand their nature, structure and the occurrence of characteristic patterns.
Unfortunately, such studies are often limited to easily-computable local properties, because of the algorithmic efforts required to carry out the computation of global features. Recently, however, new tools have been made available that allow to approximate efficiently and with a controllable precision and confidence global properties such as the graph distance distribution.
In this talk, I will present one such tool, called HyperANF, and show some preliminary applications related to robustness and node centrality, with extensive experimental studies on real-world social networks. In particular, I will report on the results of running HyperANF on the Facebook graph and on some of its subgraphs: this is by far the largest Milgram-type experiment ever performed on a real human network (of more than 1 billion nodes).

This is joint work with Lars Backstrom, Marco Rosa and Sebastiano Vigna.


Flavio Chierichetti, Cornell University

Reconstructing Patterns of Information Diffusion from Incomplete Observations

Motivated by the spread of on-line information in general and on-line petitions in particular, recent research has raised the following combinatorial estimation problem. There is a tree T that we cannot observe directly (representing the structure along which the information has spread), and certain nodes randomly decide to make their copy of the information public. In the case of a petition, the list of names on each public copy of the petition also reveals a path leading back to the root of the tree. What can we conclude about the properties of the tree we observe from these revealed paths, and can we use the structure of the observed tree to estimate the size of the full unobserved tree T? Here we provide the first algorithm for this size estimation task, together with provable guarantees on its performance. We also establish structural properties of the observed tree, providing the first rigorous explanation for some of the unusual structural signatures present in the spread of real chain-letter petitions on the Internet.

This is joint work with Jon Kleinberg and David Liben-Nowell.

Pierre Fraigniaud, CNRS & LIAFA Universitè de Paris 7
Computing with Large Populations

We define a general model capturing the behavior of a population of anonymous agents that interact in pairs. This model captures some of the main features of opportunistic networks, in which nodes (such as the ones of a mobile ad hoc networks) meet sporadically. For its reminiscence to Population Protocol, we call our model Large-Population Protocol, or LPP. We are interested in the design of LPPs enforcing, for every F in [0,1], a fraction F of the agents to be in a specific subset of marked states, when the size of the population grows to infinity, in which case, we say that the protocol computes F. We characterize the numbers that are computable by LPPs.

Sharad Goel, Yahoo! Research
The Structure of Online Diffusion Networks

Abstract: Models of networked diffusion that are motivated by analogy with the spread of infectious disease have been applied to a wide range of social and economic adoption processes, including those related to new products, ideas, norms and behaviors. However, it is unknown how accurately these models account for the empirical structure of diffusion over networks. Here we describe the diffusion patterns arising from six online domains, ranging from communications platforms to networked games to microblogging services, each involving distinct types of content and modes of sharing. We find strikingly similar patterns across all domains. In particular, the vast majority of cascades are small, and are described by a handful of simple tree structures that terminate within one degree of an initial adopting "seed." In addition we find that structures other than these account for only a tiny fraction of total adoptions, implying that adoptions resulting from chains of referrals are extremely rare. Finally, even for the largest cascades that we observe, we find that the bulk of adoptions take place within one degree a few dominant individuals. Together, these observations show that online diffusion patterns violate core assumptions of prevailing theoretical models, and suggest new directions for diffusion modeling.

This is joint work with Duncan Watts and Dan Goldstein.

Thomas Karagiannis, Microsoft
Using social graphs to optimize large-scale distributed services.

There has been considerable work over the last few years on studying and understanding the properties of social networking applications and their associated implicit or explicit social graphs.
Once these underlying properties are identified, using them in systems design and optimization becomes feasible. In this talk, I will present one such example, where social interactions within an organization are exploited to optimize a large-scale enterprise e-mail system. In particular, I will discuss how tracking the implicit social graph of e-mail communications of an organization, and co-locating clusters of strongly connected users on the same servers can significantly reduce storage and bandwidth requirements.

Anne-Marie Kermarrec, INRIA
P2P instant news items recommender

WhatsUp is an instant news system aimed for a large scale network with no central bottleneck, single point of failure or censorship authority. Users express their opinions about the news items they receive by operating a like-dislike button. WhatsUp’s collaborative filtering scheme leverages these opinions to dynamically maintain an implicit social network and ensures that users subsequently receive news that are likely to match their interests. Users with similar tastes are clustered using a similarity metric reflecting long-standing and emerging (dis)interests. News items are disseminated through a heterogeneous epidemic protocol that (a) biases the choice of the targets towards those with similar interests and (b) amplifies the dissemination based on the interest of every actual news item. The push and asymmetric nature of the network created by WhatsUp provides a natural support to limit privacy breaches.
The evaluation of through large-scale simulations, a ModelNet emulation on a cluster and a PlanetLab deployment on real traces collected both from Digg as well as from a real survey, show that WhatsUp consistently outperforms centralized and decentralized alternatives in terms of accurate and complete delivery of relevant news.


Vahab Mirrokni, Google
Overlapping Clustering: Conductance minimization and Distributed Computation

I will discuss overlapping clustering of large social networks. The talk has three parts: The first part consists of approximation algorithms capturing overlapping clustering while minimizing average and maximum conductance of the clusters. The second part promotes the use of such overlapping clustering in distributed computation and in particular the computation of PageRank vectors in a distributed infrastructure. Finally the third part describes implementation and results of a large-scale overlapping clustering algorithm applied to community discovery over Youtube videos using the co-watched graph. Here, we manage to cluster a graph of 150 million nodes in 8 hours.


Milan Vojnovic, Microsoft
Bargaining Dynamics in Social Exchange Networks

We consider local and decentralized dynamics that converge to stable and balanced bargaining outcomes in social exchange networks. In a social exchange network, each pair of agents bargain on how to share an associated wealth should a partnership between these two agents is realized, where each agent has an endogenous outside option to partner with another agent. We will consider conditions for convergence of the associated bargaining processes to stable and balanced outcomes and their rate of convergence. These dynamical systems are typically nonlinear, however, we will show that so called edge-balanced dynamics is linear or becomes eventually linear for elementary graphs of the Kleinberg-Tardos graph decomposition, which allows for establishing quadratic convergence time in the number of agents for these elementary graph structures.



sponsored by:
logo sapienza         logo microsoft research        logo cini consorzio interuniversitario per l'informatica