Nan Du
Christos Faloutsos
Leman Akoglu
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.
Supplemental Material
- C. C. Aggarwal and P. S. Yu. Outlier detection with uncertain data. In SDM, pages 483--493, 2008.Google Scholar
Cross Ref
- S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty. On nash equilibria for a network creation game. In SODA,pages 89--98, 2006. Google ScholarDigital Library
- R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47, 2002.Google ScholarCross Ref
- B. Wu and D. B. Davison Identifying link farm spam pages. In WWW 2005, pages 820--829, 2005. Google ScholarDigital Library
- A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, October 1999.Google ScholarCross Ref
- Z. Bi, C. Faloutsos, and F. Korn. The"DGX distribution for mining massive, skewed data. SIGKDD 2001, pages 17--26 Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Chakrabarti and C. Faloutsos. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv., 38(1), 2006. Google ScholarDigital Library
- V. Chandola, A. Banerjee, and V. Kumar. Anomaly detection: A survey. To Appear in ACM Computing Survey. Google ScholarDigital Library
- L.-N. David and K. Jon. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019--1031, 2007. Google ScholarDigital Library
- E. D. Demaine, M. Hajiaghayi, H. Mahini, and M. Zadimoghaddam. The price of anarchy in network creation games. In PODC, pages 292--298, 2007. Google ScholarDigital Library
- N. Du, B. Wu, and B. Wang. A parallel algorithm for enumerating all maximal cliques in complex networks. In ICDM2006 Mining Complex Data Workshop, pages 320--324. Google ScholarDigital Library
- Z. Elena, K. Aleksander, and G. Lise. Trusting spam reporters: A reporter-based reputation system for email filtering. ACM Trans. Inf. Syst., 27(1), 2008. Google ScholarDigital Library
- P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungary. Acad. Sci., 5:17--61, 1960.Google Scholar
- E. Even-Dar, M. J. Kearns, and S. Suri. A network formation game for bipartite exchange economies. In SODA, pages 697--706, 2007. Google ScholarDigital Library
- A. Fabrikant, A. Luthra, E. N. Maneva, C. H. Papadimitriou, and S. Shenker. On a network creation game. In PODC, pages 347--351, 2003. Google ScholarDigital Library
- J. Leskovec, L. Backstorm, R. Kumar, and A. Tomkins Microscopic evolution of social networks. In SIGKDD 2008, pages 462--470. Google ScholarDigital Library
- Y. Koren. Tutorial on recent progress in collaborative filtering. In RecSys 2008. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- J.-G. Lee, J. Han, and X. Li. Trajectory outlier detection: A partition-and-detect framework. In ICDE 2008, pages 140--149. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In SIGKDD 2005, pages 177--187. Google ScholarDigital Library
- M. McGlohon, L. Akoglu, and C. Faloutsos. Weighted graphs and disconnected components: patterns and a generator. In SIGKDD 2008. Google ScholarDigital Library
- W. Michael and H. Mattord. Principles of Information Secuirty. Thomson, Canada.Google Scholar
- M. Mitzenmacher. Dynamic models for file sizes and double pareto distributions. 2002.Google Scholar
- A. A. Nanavati, S. Gurumurthy, G. Das, D. Chakraborty, K. Dasgupta, S. Mukherjea, and A. Joshi. In CIKM 2006.Google Scholar
- J. F. Nash. Non-cooperative games. Annals of Mathematics, 54, 286--295, 1951.Google ScholarCross Ref
- M. E. J. Newman. Power laws, pareto distributions and zipf's law. May 2006.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- W. Reed and M. Jorgensen. The double pareto-lognormal distribution a new parametric model for size distribution. 2004.Google Scholar
- M. Seshadri, S. Machiraju, A. Sridharan, J. Bolot, C. Faloutsos, and J. Leskove. In SIGKDD 2008.Google Scholar
- J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. In ICDM, pages 418--425, 2005. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, Cambridge, 1994.Google ScholarCross Ref
- D. Watts. Small Worlds:The Dynamics of Networks between Order and Randomness. Princeton University Press, 1999. Google ScholarDigital Library
- D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393(6684):440--442, June 1998.Google ScholarCross Ref
- D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, June 1998.Google ScholarCross Ref
Index Terms
- Large human communication networks: patterns and a utility-driven generator
Recommendations
Cliques in the union of graphs
Let B and R be two simple graphs with vertex set V, and let G ( B , R ) be the simple graph with vertex set V, in which two vertices are adjacent if they are adjacent in at least one of B and R. For X V , we denote by B | X the subgraph of B induced by ...
Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
AbstractA class of graphs is χ-bounded if there is a function f such that χ ( G ) ≤ f ( ω ( G ) ) for every induced subgraph G of every graph in the class, where χ , ω denote the chromatic number and clique number of G respectively. In 1987, ...
Biclique graphs and biclique matrices
A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,-1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in ...
Comments