The structure of information pathways in a social communication network

ABSTRACT

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.

REFERENCES

• 1: L. Adamic and E. Adar. How to search a social network. Social Networks, 27(3):187--203, 2005.
• 2: L. A. Adamic, B. A. Huberman. Information dynamics in the networked world. Springer Lec. Notes. Phys. 650(2004).
• 3: E. Adar, L. Zhang, L. A. Adamic, and R. M. Lukose. Implicit structure and the dynamics of blogspace. In Workshop on the Weblogging Ecosystem, 2004.
• 4: R. Albert, H. Jeong, and A.-L. Barabási. Error and attack tolerance in complex networks. Nature, 406:378--382, 2000.
• 5: K. Berman. Vulnerability of scheduled networks and a generalization of Menger's theorem. Networks, 28(1996).
• 6: Eddie Cheng , Jerrold W. Grossman , Marc J. Lipman, Time-stamped graphs and their associated influence digraphs, Discrete Applied Mathematics, v.128 n.2-3, p.317-335, 01 June 2003 [doi>10.1016/S0166-218X(02)00497-3]
• 7: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 8: P. Dodds, R. Muhamad, and D. Watts. An experimental study of search in global social networks. Science, 301(2003).
• 9: J.-P. Eckmann, E. Moses, and D. Sergi. Entropy of dialogues creates coherent structures in e-mail traffic. Proc. Natl. Acad. Sci. USA, 101:14333--14337, 2004.
• 10: D. Gibson. Concurrency and commitment: Network scheduling and its consequences for diffusion. Journal of Mathematical Sociology, 29(4):295--323, 2005.
• 11: M. Granovetter. The strength of weak ties. American Journal of Sociology, 78:1360--1380, 1973.
• 12: M. Granovetter. The strength of weak ties: A network theory revisited. Sociological Theory, 1:201--233, 1983.
• 13: Daniel Gruhl , R. Guha , David Liben-Nowell , Andrew Tomkins, Information diffusion through blogspace, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988739]
• 14: P. Holme. Network reachability of real-world contact sequences. Physical Review E, 71:046119, 2005.
• 15: David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.504-513, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335364]
• 16: B. Klimt and Y. Yang. The Enron corpus: A new dataset for email classification research. In Proc. 15th European Conference on Machine Learning, pages 217--226, 2004.
• 17: G. Kossinets. Effects of missing data in social networks. Social Networks, 28:247--268, 2006.
• 18: G. Kossinets and D. Watts. Empirical analysis of an evolving social network. Science, 311:88--90, 2006.
• 19: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 20: E. Laumann, P. Marsden, D. Prensky. The boundary specification problem in network analysis. In R. S. Burt and M. J. Minor, editors, Applied Network Analysis, 1983.
• 21: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, Proceedings of the 7th ACM conference on Electronic commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134732]
• 22: Jure Leskovec , Eric Horvitz, Planetary-scale views on a large instant-messaging network, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367620]
• 23: J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, and M. Hurst. Cascading behavior in large blog graphs. In Proc. SIAM International Conference on Data Mining, 2007.
• 24: D. Liben-Nowell and J. Kleinberg. Tracing information flow on a global scale using Internet chain-letter data. Proc. Natl. Acad. Sci. USA, 105(12):4633--4638, Mar. 2008.
• 25: F. Mattern. Virtual time and global states of distributed systems. Workshop on Parallel and Distributed Algs. 1989.
• 26: V. Nabokov. The Gift. (English translation by M. Scammel and V. Nabokov.) Vintage, 1963.
• 27: J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, and A.-L. Barabasi. Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. USA, 104:7332--7336, 2007.
• 28: E. F. Taylor and J. A. Wheeler. Spacetime Physics: Introduction to Special Relativity. W.H. Freeman, 1992.
• 29: J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32(4):425--443, 1969.
• 30: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 31: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 32: H. C. White. Everyday life in stochastic networks. Sociological Inquiry, 43:43--49, 1973.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Measurement, Theory

Keywords:
communication latency, social network, strength of weak ties