The structure of information pathways in a social communication network

By Gregory Kossinets, Jon M. Kleinberg, Duncan J. Watts. Knowledge Discovery and Data Mining, 2008

369 citations recorded by the source corpus.

Social networks are of interest to researchers in part because they are thought to mediate the flow of information in communities and organizations. Here we study the temporal dynamics of communication using on-line data, including e-mail communication among the faculty and staff of a large university over a two-year period. We formulate a temporal notion of "distance" in the underlying social network by measuring the minimum time required for information to spread from one node to another - a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges - a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/9c91bc079a4f7ae8a931df0d4521232b782695fd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Path Problems in Temporal Graphs (2014, background): “Later a number of different types of paths were proposed [1, 11, 12, 14, 15, 16, 17, 21] based on the concept of temporal path.”
Temporal Networks (2011, background): “[98] define the ‘‘distance’’ between two vertices as the shortest duration of any time-respecting path between them.”
Time-varying graphs and dynamic networks (2010, background): “In [49] the authors study the temporal dynamics of communication over a dataset of on-line communications and emails over a two years period.”
Center of Attention: How Facebook Users Allocate Attention across Friends (2011, result): “This is also the distinction that motivates our work, although our focus differs from earlier papers to address this issue: Kossinets et al. (2008) study how link activity can lead to different pathways for information flow over multi-step paths, and Wilson et al. (2009) focus on aggregate measures…”
What's in a crowd? Analysis of face-to-face behavioral networks (2010, background): “…the diameter of the partially aggregated network (orange path), a ﬁrst signature of the fact that the fastest paths between two individuals, which are the ones followed by the spreading process, do not coincide with the shortest path over the partially aggregated network (Kossinets et al., 2008).”
Temporal motifs in time-dependent networks (2011, background): “This temporal aspect turns out to be crucial for processes like spreading of information and electronic viruses in communication networks [9, 10, 11, 12, 13, 14, 15], epidemiological applications [16, 17], and signal processing in the brain (see, e.g. , [18, 19]).”
K-isomorphism: privacy preserving network publication against structural attacks (2010, background): “A considerable amount of research has been conducted on social network analysis [3, 15, 18].”
How Does the Data Sampling Strategy Impact the Discovery of Information Diffusion in Social Media? (2010, background): “…from recommendation systems, online advertising, user behavior prediction and disease containment (Kempe, Kleinberg, and Tardos 2003), (Gruhl et al. 2004), (Song et al. 2006), (Anagnostopoulos, Kumar, and Mahdian 2008), (Kossinets, Kleinberg, and Watts 2008), (Liben-Nowell and Kleiberg 2008).”