Large human communication networks: patterns and a utility-driven generator

ABSTRACT

Given a real, and weighted person-to-person network which changes over time, what can we say about the cliques that it contains? Do the incidents of communication, or weights on the edges of a clique follow any pattern? Real, and in-person social networks have many more triangles than chance would dictate. As it turns out, there are many more cliques than one would expect, in surprising patterns.

In this paper, we study massive real-world social networks formed by direct contacts among people through various personal communication services, such as Phone-Call, SMS, IM etc. The contributions are the following: (a) we discover surprising patterns with the cliques, (b) we report power-laws of the weights on the edges of cliques, (c) our real networks follow these patterns such that we can trust them to spot outliers and finally, (d) we propose the first utility-driven graph generator for weighted time-evolving networks, which match the observed patterns. Our study focused on three large datasets, each of which is a different type of communication service, with over one million records, and spans several months of activity.

REFERENCES

• 1: C. C. Aggarwal and P. S. Yu. Outlier detection with uncertain data. In SDM, pages 483--493, 2008.
• 2: Susanne Albers , Stefan Eilts , Eyal Even-Dar , Yishay Mansour , Liam Roditty, On nash equilibria for a network creation game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.89-98, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109568]
• 3: R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47, 2002.
• 4: Baoning Wu , Brian D. Davison, Identifying link farm spam pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062762]
• 5: A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, October 1999.
• 6: Zhiqiang Bi , Christos Faloutsos , Flip Korn, The "DGX" distribution for mining massive, skewed data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.17-26, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502521]
• 7: F. Cazals and C. Karande. Reporting maximal cliques: new insights into an old problem. Research Report, http://cgal.inria.fr/Publications/2005/CK05b, (5615), 2005.
• 8: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 9: Varun Chandola , Arindam Banerjee , Vipin Kumar, Anomaly detection: A survey, ACM Computing Surveys (CSUR), v.41 n.3, p.1-58, July 2009 [doi>10.1145/1541880.1541882]
• 10: David Liben-Nowell , Jon Kleinberg, The link-prediction problem for social networks, Journal of the American Society for Information Science and Technology, v.58 n.7, p.1019-1031, May 2007 [doi>10.1002/asi.v58:7]
• 11: Erik D. Demaine , MohammadTaghi Hajiaghayi , Hamid Mahini , Morteza Zadimoghaddam, The price of anarchy in network creation games, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281142]
• 12: Nan Du , Bin Wu , Liutong Xu , Bai Wang , Xin Pei, A Parallel Algorithm for Enumerating All Maximal Cliques in Complex Network, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.320-324, December 18-22, 2006 [doi>10.1109/ICDMW.2006.17]
• 13: Elena Zheleva , Aleksander Kolcz , Lise Getoor, Trusting spam reporters: A reporter-based reputation system for email filtering, ACM Transactions on Information Systems (TOIS), v.27 n.1, p.1-27, December 2008 [doi>10.1145/1416950.1416953]
• 14: P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungary. Acad. Sci., 5:17--61, 1960.
• 15: Eyal Even-Bar , Michael Kearns , Siddharth Suri, A network formation game for bipartite exchange economies, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-706, January 07-09, 2007, New Orleans, Louisiana
• 16: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 17: Jure Leskovec , Lars Backstrom , Ravi Kumar , Andrew Tomkins, Microscopic evolution of social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401948]
• 18: Yehuda Koren, Tutorial on recent progress in collaborative filtering, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454067]
• 19: N. Laoutaris, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng. Bounded budget connection games or how to make friends and influence people on a budget. CoRR, 2008.
• 20: Jae-Gil Lee , Jiawei Han , Xiaolei Li, Trajectory Outlier Detection: A Partition-and-Detect Framework, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.140-149, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497422]
• 21: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 22: Mary McGlohon , Leman Akoglu , Christos Faloutsos, Weighted graphs and disconnected components: patterns and a generator, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401955]
• 23: W. Michael and H. Mattord. Principles of Information Secuirty. Thomson, Canada.
• 24: M. Mitzenmacher. Dynamic models for file sizes and double pareto distributions. 2002.
• 25: A. A. Nanavati, S. Gurumurthy, G. Das, D. Chakraborty, K. Dasgupta, S. Mukherjea, and A. Joshi. In CIKM 2006.
• 26: J. F. Nash. Non-cooperative games. Annals of Mathematics, 54, 286--295, 1951.
• 27: M. E. J. Newman. Power laws, pareto distributions and zipf's law. May 2006.
• 28: J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, A. M. de Menezes, K. Kaski, A.-L. Barabasi, and J. Kertesz. Analysis of a large-scale weighted network of one-to-one human communication. New J. Phys., 9(6):179, 2007.
• 29: 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. PNAS, 104(18):7332--7336, May 2007.
• 30: W. Reed and M. Jorgensen. The double pareto-lognormal distribution a new parametric model for size distribution. 2004.
• 31: M. Seshadri, S. Machiraju, A. Sridharan, J. Bolot, C. Faloutsos, and J. Leskove. In SIGKDD 2008.
• 32: Jimeng Sun , Huiming Qu , Deepayan Chakrabarti , Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.418-425, November 27-30, 2005 [doi>10.1109/ICDM.2005.103]
• 33: S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, Cambridge, 1994.
• 34: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 35: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393(6684):440--442, June 1998.
• 36: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, June 1998.

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
cliques, graph generators, social networks