Graph mining: Laws, generators, and algorithms

ABSTRACT

How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: “How can we generate synthetic but realistic graphs?” To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.

REFERENCES

• 1: Adamic, L. A. and Huberman, B. A. 2000. Power-law distribution of the World Wide Web. Science 287, 2115.
• 2: Lada A. Adamic , Bernardo A. Huberman, The Web's hidden order, Communications of the ACM, v.44 n.9, p.55-60, Sept. 2001 [doi>10.1145/383694.383707]
• 3: Adamic, L. A., Lukose, R. M., Puniyani, A. R., and Huberman, B. A. 2001. Search in power-law networks. Physical Rev. E 64, 4, 046135 1--8.
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 5: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 6: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 7: Albert, R. and Barabási, A.-L. 2000. Topology of evolving networks: local events and universality. Physical Rev. Lett. 85, 24, 5234--5237.
• 8: Albert, R. and Barabási, A.-L. 2002. Statistical mechanics of complex networks. Rev. Modern Physics 74, 1, 47--97.
• 9: Albert, R., Jeong, H., and Barabási, A.-L. 1999. Diameter of the World-Wide Web. Nature 401, 130--131.
• 10: Albert, R., Jeong, H., and Barabási, A.-L. 2000. Error and attack tolerance of complex networks. Nature 406, 378--381.
• 11: Noga Alon, Spectral Techniques in Graph Algorithms, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.206-215, April 20-24, 1998
• 12: Alon, N., Yuster, R., and Zwick, U. 1997. Finding and counting given length cycles. Algorithmica 17, 3, 209--223.
• 13: Amaral, L. A. N., Scala, A., Barthélémy, M., and Stanley, H. E. 2000. Classes of small-world networks. Proceedings of the National Academy of Sciences 97, 21, 11149--11152.
• 14: Ricardo Baeza-Yates , Barbara Poblete, Evolution of the Chilean Web Structure Composition, Proceedings of the First Conference on Latin American Web Congress, p.11, November 10-12, 2003
• 15: Bailey, N. T. J. 1974. The Mathematical Theory of Infectious Diseases and its Applications 2nd Ed. Charles Griffin, London, UK.
• 16: Baker, W. E. and Faulkner, R. R. 1993. The social organization of conspiracy: Illegal networks in the Heavy Electrical Equipment industry. Amer. Sociolog. Rev. 58, 6, 837--860.
• 17: Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 18: Barabási, A.-L. 2002. Linked: The New Science of Networks 1st Ed. Perseus Books Group, New York, NY.
• 19: Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.
• 20: Barabási, A.-L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., and Vicsek, T. 2002. Evolution of the social network of scientific collaborations. Physica A 311, 590--614.
• 21: Jan Beirlant , Tertius de Wet , Yuri Goegebeur, A goodness-of-fit statistic for Pareto-type behaviour, Journal of Computational and Applied Mathematics, v.186 n.1, p.99-116, 1 Febraury 2006 [doi>10.1016/j.cam.2005.01.036]
• 22: Ben-Hur, A. and Guyon, I. 2003. Detecting stable clusters using principal component analysis. In Methods in Molecular Biology. M. J. Brownstein and A. Khudorsky, Eds. Humana Press, Totowa, NJ, 159--182.
• 23: N. Berger , C. Borgs , J. T. Chayes , R. M. D'souza , R. D. Kleinberg, Degree Distribution of Competition-Induced Preferential Attachment Graphs, Combinatorics, Probability and Computing, v.14 n.5-6, p.697-721, November 2005 [doi>10.1017/S0963548305006930]
• 24: Berry, M. W. 1992. Large scale singular value computations. Inte. J. Supercomput. Applic. 6, 1, 13--49.
• 25: 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]
• 26: Bianconi, G. and Barabási, A.-L. 2001. Competition and multiscaling in evolving networks. Europhysics Letters 54, 4, 436--442.
• 27: Boguñá, M. and Pastor-Satorras, R. 2002. Epidemic spreading in correlated complex networks. Physical Rev. E 66, 4, 047104.
• 28: Boldi, P., Codenotti, B., Santini, M., and Vigna, S. 2002. Structural properties of the African Web. In International World Wide Web Conference. ACM Press, New York, NY.
• 29: Bollobás, B. 1985. Random Graphs. Academic Press, London, UK.
• 30: Béla Bollobás , Christian Borgs , Jennifer Chayes , Oliver Riordan, Directed scale-free graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 31: Bollobás, B. and Riordan, O. 2002. The diameter of a scale-free random graph. Combinatorica.
• 32: Bonacich, P. 1987. Power and centrality: A family of measures. Amer. J. Sociol. 92, 5 (Mar.), 1170--1182.
• 33: Borgatti, S. 2002. The key player problem. In Proceedings of the National Academy of Sciences Workshop on Terrorism. National Academy of Sciences, Washington DC.
• 34: Borgatti, S. and Everett, M. G. 1989. The class of all regular equivalences: Algebraic structure and computation. Social Networks 11, 65--88.
• 35: Borgatti, S. and Everett, M. G. 1999. Models of core/periphery structures. Social Networks 21, 275--295.
• 36: Borgatti, S., Everett, M. G., and Freeman, L. C. 1999. UCINET V User's Guide. Analytic Technologies.
• 37: Christian Borgs , Jennifer Chayes , Mohammad Mahdian , Amin Saberi, Exploring the community structure of newsgroups, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1016914]
• 38: Brandes, U., Gaertler, M., and Wagner, D. 2003. Experiments on graph clustering algorithms. In European Symposium on Algorithms. Springer Verlag, Berlin, Germany.
• 39: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 40: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 41: Bu, T. and Towsley, D. 2002. On distinguishing between Internet power law topology generators. In IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 42: Burt, R. S. 1992. Structural Holes. Harvard University Press, Cambridge, MA.
• 43: Burt, R. S. 2001. Structural holes versus network closure as social capital. In Social Capital: Theory and Research. N. Lin, K. S. Cook, and R. S. Burt, Eds. Aldine de Gruyter, Hawthorne, NY.
• 44: Callaway, D. S., Newman, M. E. J., Strogatz, S. H., and Watts, D. J. 2000. Network robustness and fragility: Percolation on random graphs. Physical Rev. Lett. 85, 25, 5468--5471.
• 45: Calvert, K. L., Doar, M. B., and Zegura, E. W. 1997. Modeling Internet topology. IEEE Comm. 35, 6, 160--163.
• 46: Carlson, J. M. and Doyle, J. 1999. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Rev. E 60, 2, 1412--1427.
• 47: Deepayan Chakrabarti, AutoPart: parameter-free graph partitioning and outlier detection, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.112-124, September 20-24, 2004, Pisa, Italy
• 48: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]
• 49: Chakrabarti, D., Zhan, Y., and Faloutsos, C. 2004. R-MAT: A recursive model for graph mining. In SIAM Data Mining Conference. SIAM, Philadelphia, PA.
• 50: Soumen Chakrabarti, Recent results in automatic Web resource discovery, ACM Computing Surveys (CSUR), v.31 n.4es, Dec. 1999 [doi>10.1145/345966.346007]
• 51: Soumen Chakrabarti , Kunal Punera , Mallela Subramanyam, Accelerated focused crawling through online relevance feedback, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511466]
• 52: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1623-1640, May 17, 1999
• 53: Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S., and Willinger, W. 2001. The origin of power laws in Internet topologies revisited. In IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 54: Clauset, A., Newman, M. E. J., and Moore, C. 2004. Finding community structure of very large networks. Physical Rev. E 70, 066111.
• 55: Coleman, J. S. 1988. Social capital in the creation of human capital. Amer. J. Sociol. 94, S95--S121.
• 56: Colin Cooper , Alan Frieze, A general model of web graphs, Random Structures & Algorithms, v.22 n.3, p.311-335, May 2003 [doi>10.1002/rsa.10084]
• 57: Colin Cooper , Alan Frieze, The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence, Combinatorics, Probability and Computing, v.13 n.3, p.319-337, May 2004 [doi>10.1017/S096354830400611X]
• 58: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 59: Cross, R., Borgatti, S., and Parker, A. 2002. Making invisible work visible: Using social network analysis to support strategic collaboration. CA. Manag. Rev. 44, 2, 25--46.
• 60: Mark E. Crovella , Murad S. Taqqu, Estimating the heavy tail index from scaling properties, Methodology and Computing in Applied Probability, v.1 n.1, p.55-79, July 1999 [doi>10.1023/A:1010012224103]
• 61: de Solla Price, D. J. 1976. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soci. Inform. Science 27, 292--306.
• 62: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807]
• 63: Dehaspe, L., Toivonen, H., and King, R. D. 1998. Finding frequent substructures in chemical compounds. In Conference of the ACM Special Interest Group on Knowledge Discovery and Data Mining. ACM Press, New York, NY.
• 64: Stephen Dill , Ravi Kumar , Kevin S. McCurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.69-78, September 11-14, 2001
• 65: Dombroski, M., Fischbeck, P., and Carley, K. M. 2003. Estimating the shape of covert networks. In Proceedings of the 8th International Command and Control Research and Technology Symposium.
• 66: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 67: Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. 2002. Pseudofractal scale-free web. Physical Rev. E 65, 6, 066122.
• 68: Dorogovtsev, S. N. and Mendes, J. F. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford, UK.
• 69: Dorogovtsev, S. N., Mendes, J. F., and Samukhin, A. N. 2000. Structure of growing networks with preferential linking. Physical Rev. Lett. 85, 21, 4633--4636.
• 70: Dorogovtsev, S. N., Mendes, J. F., and Samukhin, A. N. 2001. Giant strongly connected component of directed networks. Physical Rev. E 64, 025101 1--4.
• 71: Doyle, J. and Carlson, J. M. 2000. Power laws, highly optimized tolerance, and generalized source coding. Physical Rev. Lett. 84, 24 (June), 5656--5659.
• 72: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 73: Saso (Ed.) Dzeroski , Nada Lavrac , Saso Dzeroski, Relational Data Mining, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 74: Erdős, P. and Rényi, A. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Acadamy of Science 5, 17--61.
• 75: Erdős, P. and Rényi, A. 1961. On the strength of connectedness of random graphs. Acta Mathematica Scientia Hungary 12, 261--267.
• 76: Everitt, B. S. 1974. Cluster Analysis. John Wiley, New York, NY.
• 77: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 78: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 79: Feuerverger, A. and Hall, P. 1999. Estimating a tail exponent by modelling departure from a Pareto distribution. Annals Statist. 27, 2, 760--781.
• 80: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 81: Freeman, L. C. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1, 35--41.
• 82: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 83: C. Lee Giles , Kurt D. Bollacker , Steve Lawrence, CiteSeer: an automatic citation indexing system, Proceedings of the third ACM conference on Digital libraries, p.89-98, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276685]
• 84: Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. In Proceedings of the National Academy of Sciences. Vol. 99. National Academy of Sciences, Washington DC.
• 85: Glover, F. 1989. Tabu search---part 1. ORSA J. Comput. 1, 3, 190--206.
• 86: Goh, K.-I., Oh, E., Jeong, H., Kahng, B., and Kim, D. 2002. Classificaton of scale-free networks. In Proceedings of the National Academy of Sciences. Vol. 99. National Academy of Sciences, Washington DC, 12583--12588.
• 87: Goldstein, M. L., Morris, S. A., and Yen, G. G. 2004. Problems with fitting to the power-law distribution. European Physics J. B 41, 255--258.
• 88: Govindan, R. and Tangmunarunkit, H. 2000. Heuristics for Internet map discovery. In IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 1371--1380.
• 89: Granovetter, M. S. 1973. The strength of weak ties. Amer. J. Sociol. 78, 6 (May), 1360--1380.
• 90: Hanneman, R. A. and Riddle, M. 2005. Introduction to social network methods. http://faculty.ucr.edu/hanneman/nettext/.
• 91: Hill, B. M. 1975. A simple approach to inference about the tail of a distribution. Annals Statist. 3, 5, 1163--1174.
• 92: Holder, L., Cook, D., and Djoko, S. 1994. Substructure discovery in the SUBDUE system. In National Conference on Artificial Intelligence Workshop on Knowledge Discovery in Databases. AAAI Press, Menlo Park, CA, 169--180.
• 93: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 94: Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., and Barabási, A.-L. 2000. The large-scale organization of metabolic networks. Nature 407, 6804, 651--654.
• 95: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 96: Karypis, G. and Kumar, V. 1998. Multilevel algorithms for multi-constraint graph partitioning. Tech. Rep. 98-019, University of Minnesota.
• 97: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 98: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 99: Kephart, J. O. and White, S. R. 1991. Directed-graph epidemiological models of computer viruses. In IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press, Los Alamitos, CA.
• 100: Jeffrey O. Kephart , Steve R. White, Measuring and Modeling Computer Virus Prevalence, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.2, May 24-26, 1993
• 101: Killworth, P. D. and Bernard, H. R. 1978. Reverse small world experiment. Social Networks 1, 2, 103--210.
• 102: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 103: Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, Cornell University, Ithaca, NY, 1999
• 104: Kleinberg, J. 2001. Small world phenomena and the dynamics of information. In Neural Information Processing Systems Conference. MIT Press, Cambridge, MA.
• 105: Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. The web as a graph: Measurements, models and methods. In International Computing and Combinatorics Conference. Springer, Berlin, Germany.
• 106: Krapivsky, P. L. and Redner, S. 2001. Organization of growing random networks. Physical Rev. E 63, 6, 066123 1--14.
• 107: Krebs, V. E. 2001. Mapping networks of terrorist cells. Connections 24, 3, 43--52.
• 108: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 109: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 110: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 111: Michihiro Kuramochi , George Karypis, Discovering Frequent Geometric Subgraphs, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.258, December 09-12, 2002
• 112: Leskovec, J., Chakrabarti, D., Kleinberg, J., and Faloutsos, C. 2005. Realistic, mathematically tractable graph generation and evolution, using Kronecker Multiplication. In Conference on Principles and Practice of Knowledge Discovery in Databases. Springer, Berlin, Germany.
• 113: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding 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]
• 114: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 115: McGovern, A. and Jensen, D. 2003. Identifying predictive structures in relational data using multiple instance learning. In International Conference on Machine Learning. AAAI Press, Menlo Park, CA.
• 116: Medina, A., Matta, I., and Byers, J. 2000. On the origin of power laws in Internet topologies. In Conference of the ACM Special Interest Group on Data Communications (SIGCOMM). ACM Press, New York, NY, 18--34.
• 117: Milena Mihail , Christos H. Papadimitriou, On the Eigenvalue Power Law, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.254-262, September 13-15, 2002
• 118: Milgram, S. 1967. The small-world problem. Psychology Today 2, 60--67.
• 119: Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovshii, D., and Alon, U. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 824--827.
• 120: Mitzenmacher, M. 2001. A brief history of generative models for power law and lognormal distributions. In Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing. UIUC Press, Urbana-Champaign, IL.
• 121: Alan L. Montgomery , Christos Faloutsos, Identifying Web Browsing Trends and Patterns, Computer, v.34 n.7, p.94-95, July 2001 [doi>10.1109/2.933515]
• 122: Moody, J. 2001. Race, school integration, and friendship segregation in America. Amer. J. Sociol. 107, 3, 679--716.
• 123: Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 167--256.
• 124: Newman, M. E. J. 2005. Power laws, pareto distributions and Zipf's law. Contemp. Physics 46, 323--351.
• 125: Newman, M. E. J., Forrest, S., and Balthrop, J. 2002. Email networks and the spread of computer viruses. Physical Rev. E 66, 3, 035101 1--4.
• 126: Newman, M. E. J., Girvan, M., and Farmer, J. D. 2002. Optimal design, robustness and risk aversion. Physical Rev. Lett. 89, 2, 028301 1--4.
• 127: Newman, M. E. J., Strogatz, S. H., and Watts, D. J. 2001. Random graphs with arbitrary degree distributions and their applications. Physical Rev. E 64, 2, 026118 1--17.
• 128: Nijssen, S. and Kok, J. 2001. Faster association rules for multiple relations. In International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Francisco, CA.
• 129: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 130: Palmer, C. and Steffan, J. G. 2000. Generating network topologies that obey power laws. In IEEE Global Telecommunications Conference. IEEE Computer Society Press, Los Alamitos, CA.
• 131: Gopal Pandurangan , Prabhakar Raghavan , Eli Upfal, Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.330-339, August 15-17, 2002
• 132: Pastor-Satorras, R., Vásquez, A., and Vespignani, A. 2001. Dynamical and correlation properties of the Internet. Physical Rev. Lett. 87, 25, 258701 1--4.
• 133: Pastor-Satorras, R. and Vespignani, A. 2001b. Epidemic dynamics and endemic states in complex networks. Physical Rev. E 63, 6, 066117 1--8.
• 134: Pastor-Satorras, R. and Vespignani, A. 2001a. Epidemic spreading in scale-free networks. Physical Rev. Lett. 86, 14, 3200--3203.
• 135: Pastor-Satorras, R. and Vespignani, A. 2002a. Epidemic dynamics in finite size scale-free networks. Physical Rev. E 65, 3, 035108 1--4.
• 136: Pastor-Satorras, R. and Vespignani, A. 2002b. Immunization of complex networks. Physical Rev. E 65, 3, 036104 1--8.
• 137: Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L. 2002. Winners don't take all: Characterizing the competition for links on the Web. Proceedings of the National Academy of Sciences 99, 8, 5207--5211.
• 138: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 139: Ravasz, E. and Barabási, A.-L. 2002. Hierarchical organization in complex networks. Physical Rev. E 65, 026112 1--7.
• 140: Redner, S. 1998. How popular is your paper? an empirical study of the citation distribution. European Physics J. B 4, 131--134.
• 141: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 142: Michael F. Schwartz , David C. M. Wood, Discovering shared interests using graph analysis, Communications of the ACM, v.36 n.8, p.78-89, Aug. 1993 [doi>10.1145/163381.163402]
• 143: Simon, H. 1955. On a class of skew distribution functions. Biometrika 42, 3/4, 425--440.
• 144: Solé, R. V. and Montoya, J. M. 2001. Complexity and fragility in ecological networks. In Proceedings of the Royal Society of London B. Vol. 268. The Royal Society, London, UK, 2039--2045.
• 145: Sparrow, M. K. 1991. The application of network analysis to criminal intelligence: An assessment of the prospects. Social Networks 13, 3, 251--274.
• 146: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
• 147: Tangmunarunkit, H., Govindan, R., Jamin, S., Shenker, S., and Willinger, W. 2001. Network topologies, power laws, and hierarchy. Tech. Rep. 01-746, University of Southern California.
• 148: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 149: Tauro, S. L., Palmer, C., Siganos, G., and Faloutsos, M. 2001. A simple conceptual model for the Internet topology. In Global Internet. IEEE Computer Society Press, Los Alamitos, CA.
• 150: Tibshirani, R., Walther, G., and Hastie, T. 2001. Estimating the number of clusters in a dataset via the Gap statistic. J. Royal Statist. Soc., B 63, 411--423.
• 151: Travers, J. and Milgram, S. 1969. An experimental study of the Small World problem. Sociometry 32, 4, 425--443.
• 152: Tyler, J. R., Wilkinson, D. M., and Huberman, B. A. 2003. Email as Spectroscopy: Automated Discovery of Community Structure Within Organizations. Kluwer, B. V., The Netherlands.
• 153: van Dongen, S. M. 2000. Graph clustering by flow simulation. Ph.D. thesis, Univesity of Utrecht.
• 154: Satu Virtanen, Clustering the Chilean Web, Proceedings of the First Conference on Latin American Web Congress, p.229, November 10-12, 2003
• 155: Wang, Y., Chakrabarti, D., Wang, C., and Faloutsos, C. 2003. Epidemic spreading in real networks: An eigenvalue viewpoint. In Symposium on Reliable Distributed Systems. IEEE Computer Society Press, Los Alamitos, CA, 25--34.
• 156: Wasserman, S. and Faust, K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK.
• 157: Watts, D. J. 2003. Six Degrees: The Science of a Connected Age 1st Ed. W. W. Norton and Company, New York, NY.
• 158: Watts, D. J., Dodds, P. S., and Newman, M. E. J. 2002. Identity and search in social networks. Science 296, 1302--1305.
• 159: Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 440--442.
• 160: Waxman, B. M. 1988. Routing of multipoint connections. IEEE J. Select. Areas Comm. 6, 9 (Dec.), 1617--1622.
• 161: Weeks, M. R., Clair, S., Borgatti, S., Radda, K., and Schensul, J. J. 2002. Social networks of drug users in high-risk sites: Finding the connections. AIDS Behav. 6, 2, 193--206.
• 162: Winick, J. and Jamin, S. 2002. Inet-3.0: Internet Topology Generator. Tech. Rep. CSE-TR-456-02, University of Michigan, Ann Arbor, MS.
• 163: Wu, F. and Huberman, B. A. 2004. Finding communities in linear time: A physics approach. European Physics J. B 38, 2, 331--338.
• 164: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 165: Yook, S.-H., Jeong, H., and Barabási, A.-L. 2002. Modeling the Internet's large-scale topology. Proceedings of the National Academy of Sciences 99, 21, 13382--13386.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Measurement

Keywords:
Generators, graphs, patterns, social networks