The DOI matches its Crossref record; 165 of the 165 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Granovetter, M. S. (1973) · American Journal of Sociology · doi:10.1086/225469 · Cited by 40,491
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135 · cited 3×
“0 for large N BA [Barab´asi and Albert 1999] O(log N)or O( log N log log N ) CC .”
InfluentialSocial Capital in the Creation of Human Capital
Coleman, J. S. (1988) · American Journal of Sociology · doi:10.1086/228943 · Cited by 26,975
Social Capital in the Creation of Human Capital
COLEMAN, J. (2000) · Knowledge and Social Capital · doi:10.1016/b978-0-7506-7222-1.50005-2 · Cited by 21,666
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Social Network Analysis: Methods and Applications
Wasserman, S. S., & Faust, K. (1994) · Cited by 17,993
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Fast algorithms for mining association rules
Agrawal, R., & Srikant, R. (1998) · Cited by 11,307
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
Fast Algorithms for Mining Association Rules in Large Databases
Agrawal, R., & Srikant, R. (1994) · Very Large Data Bases · Cited by 9,419
Everitt, B. J., Landau, S., & Leese, M. (1974) · Cited by 9,358
Burt, R. S. (1992) · doi:10.4159/9780674029095 · Cited by 9,093
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
Estimating the Number of Clusters in a Data Set Via the Gap Statistic
Tibshirani, R., Walther, G., & Hastie, T. (2001) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/1467-9868.00293 · Cited by 6,205
Bollobás, B. (1985) · Cited by 6,196
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749
Epidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,731
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
The Evolution of Random Graphs
(1986) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/062/06 · Cited by 5,543
Power and Centrality: A Family of Measures
Bonacich, P. (1987) · American Journal of Sociology · doi:10.1086/228631 · Cited by 5,165
Glover, F. (1989) · ORSA Journal on Computing · doi:10.1287/ijoc.1.3.190 · Cited by 5,106
The Large-Scale Organization of Metabolic Networks
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35036627 · Cited by 4,972
The small-world problem: (400002009-005)
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 4,790
Colman (2022) · doi:10.1073/pnas · Cited by 4,370
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Self-citationIntroduction to Social Network Methods
Hanneman, R. A. (2001) · Cited by 3,956
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
Basic Methods in Molecular Biology
(1986) · Elsevier eBooks · doi:10.1016/b978-0-444-01082-7.x5001-2 · Cited by 3,134
A Simple General Approach to Inference About the Tail of a Distribution
Hill, B. M. (1975) · The Annals of Statistics · doi:10.1214/aos/1176343247 · Cited by 3,086
Classes of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Routing of multipoint connections
Waxman, B. M. (1988) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.12889 · Cited by 2,885
Mining the network value of customers
Domingos, P., & Richardson, M. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502525 · Cited by 2,830
ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
SIMON, H. A. (1955) · Biometrika · doi:10.1093/biomet/42.3-4.425 · Cited by 2,771
Linked: The New Science of Networks
Barabási, A.-L., & Aldana-Gonzalez, M. (2003) · Physics Today · doi:10.1063/1.1570778 · Cited by 2,724
Network Robustness and Fragility: Percolation on Random Graphs
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.5468 · Cited by 2,480
Graphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Self-citationSocial Capital: Theory and Research
Lounsbury, M., Lin, N., Cook, K., & Burt, R. S. (2002) · Contemporary Sociology · doi:10.2307/3089402 · Cited by 2,268
Models of core/periphery structures
Borgatti, S. P., & Everett, M. G. (2000) · Social Networks · doi:10.1016/s0378-8733(99)00019-2 · Cited by 2,219
Hierarchical organization in complex networks
Ravasz, E., & Barabási, A.-L. (2003) · Physical Review E · doi:10.1103/physreve.67.026112 · Cited by 2,160
Biclustering algorithms for biological data analysis: a survey
Madeira, S. C., & Oliveira, A. L. (2004) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2004.2 · Cited by 2,049
A general theory of bibliometric and other cumulative advantage processes
Price, D. D. S. (1976) · Journal of the American Society for Information Science · doi:10.1002/asi.4630270505 · Cited by 2,035
gSpan: graph-based substructure pattern mining
Yan, X., & Han, J. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1184038 · Cited by 2,013
Evolution of the social network of scientific collaborations
Barabási, A. L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., & Vicsek, T. (2002) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(02)00736-7 · Cited by 1,972
The Mathematical Theory of Infectious Diseases and its applications
Ling, N. R. (1978) · Immunology · Cited by 1,934
The small-world phenomenon: an algorithmic perspective
Kleinberg, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335325 · Cited by 1,882
An Experimental Study of the Small World Problem
Travers, J., & Milgram, S. (1969) · Sociometry · doi:10.2307/2786545 · Cited by 1,863
Linked: The New Science of Networks
Cohen, E. A., & Barabási, A.-L. (2002) · Foreign Affairs · doi:10.2307/20033300 · Cited by 1,788
Six Degrees: The Science of a Connected Age
Watts, D. J. (2003) · Cited by 1,724
Epidemic dynamics and endemic states in complex networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review E · doi:10.1103/physreve.63.066117 · Cited by 1,682
Mining knowledge-sharing sites for viral marketing
Richardson, M., & Domingos, P. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775057 · Cited by 1,612
Graph Clustering by Flow Simulation
van Dongen, S. M. (2000) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 1,595
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
How popular is your paper? An empirical study of the citation distribution
Redner, S. (1998) · The European Physical Journal B · doi:10.1007/s100510050359 · Cited by 1,509
Focused crawling: a new approach to topic-specific Web resource discovery
Chakrabarti, S., van den Berg, M., & Dom, B. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00052-3 · Cited by 1,486
Dynamical and Correlation Properties of the Internet
Pastor-Satorras, R., Vázquez, A., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.258701 · Cited by 1,466
Six degrees: the science of a connected age
(2003) · Choice Reviews Online · doi:10.5860/choice.40-6452 · Cited by 1,362
Structural Holes versus Network Closure as Social Capital
Burt, R. S. (2017) · Social Capital · doi:10.4324/9781315129457-2 · Cited by 1,358
Race, School Integration, and Friendship Segregation in America
Moody, J. (2001) · American Journal of Sociology · doi:10.1086/338954 · Cited by 1,342
Topology of Evolving Networks: Local Events and Universality
Albert, R., & Barabási, A.-L. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.5234 · Cited by 1,308
Structure of Growing Networks with Preferential Linking
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4633 · Cited by 1,307
Immunization of complex networks
Pastor-Satorras, R., & Vespignani, A. (2002) · Physical Review E · doi:10.1103/physreve.65.036104 · Cited by 1,278
R-MAT: A Recursive Model for Graph Mining
Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.43 · Cited by 1,255
Self-citationAdamic, L. A., Lukose, R. M., Puniyani, A. R., & Huberman, B. A. (2001) · Physical Review E · doi:10.1103/physreve.64.046135 · Cited by 1,203
A Brief History of Generative Models for Power Law and Lognormal Distributions
Mitzenmacher, M. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129088 · Cited by 1,188
Kuramochi, M., & Karypis, G. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989534 · Cited by 1,068
Competition and multiscaling in evolving networks
Bianconi, G., & Barabási, A.-L. (2001) · Europhysics Letters (EPL) · doi:10.1209/epl/i2001-00260-6 · Cited by 1,067
Identity and Search in Social Networks
Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002) · Science · doi:10.1126/science.1070120 · Cited by 1,052
CiteSeer: an automatic citation indexing system
Giles, C. L., Bollacker, K. D., & Lawrence, S. (1998) · Proceedings of the third ACM conference on Digital libraries - DL '98 · doi:10.1145/276675.276685 · Cited by 1,040
An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
Inokuchi, A., Washio, T., & Motoda, H. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45372-5_2 · Cited by 1,039
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
Power-Law Distribution of the World Wide Web
Adamic, L. A., & Huberman, B. A. (2000) · Science · doi:10.1126/science.287.5461.2115a · Cited by 1,015
Mapping Networks of Terrorist Cells
Krebs, V. E. (2001) · Cited by 995
Making Invisible Work Visible: Using Social Network Analysis to Support Strategic Collaboration
Cross, R., Borgatti, S. P., & Parker, A. (2002) · California Management Review · doi:10.2307/41166121 · Cited by 924
A random graph model for massive graphs
Aiello, W., Chung, F., & Lu, L. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335326 · Cited by 917
Organization of growing random networks
Krapivsky, P. L., & Redner, S. (2001) · Physical Review E · doi:10.1103/physreve.63.066123 · Cited by 871
Referral Web: combining social networks and collaborative filtering
Kautz, H., Selman, B., & Shah, M. (1997) · Communications of the ACM · doi:10.1145/245108.245123 · Cited by 847
Epidemic spreading in real networks: an eigenvalue viewpoint
Wang, Y., Chakrabarti, D., Wang, C., & Faloutsos, C. (2004) · 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings. · doi:10.1109/reldis.2003.1238052 · Cited by 837
Self-citationOn clusterings: Good, bad and spectral
Kannan, R., Vempala, S., & Vetta, A. (2004) · Journal of the ACM · doi:10.1145/990308.990313 · Cited by 834
Efficient identification of Web communities
Flake, G. W., Lawrence, S., & Giles, C. L. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347121 · Cited by 804
Complexity and fragility in ecological networks
Solé, R. V., & Montoya, M. (2001) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.2001.1767 · Cited by 799
Email networks and the spread of computer viruses
Newman, M. E. J., Forrest, S., & Balthrop, J. (2002) · Physical Review E · doi:10.1103/physreve.66.035101 · Cited by 798
On the strength of connectedness of a random graph
Erdős, P., & Rényi, A. (1964) · Acta Mathematica Academiae Scientiarum Hungaricae · doi:10.1007/bf02066689 · Cited by 785
Directed-graph epidemiological models of computer viruses
Kephart, J. O., & White, S. R. (2002) · Proceedings. 1991 IEEE Computer Society Symposium on Research in Security and Privacy · doi:10.1109/risp.1991.130801 · Cited by 769
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · 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 - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
The Social Organization of Conspiracy: Illegal Networks in the Heavy Electrical Equipment Industry
Baker, W. E., & Faulkner, R. R. (1993) · American Sociological Review · doi:10.2307/2095954 · Cited by 728
Epidemic dynamics in finite size scale-free networks
Pastor-Satorras, R., & Vespignani, A. (2002) · Physical Review E · doi:10.1103/physreve.65.035108 · Cited by 697
Heuristics for Internet map discovery
Govindan, R., & Tangmunarunkit, H. (2002) · Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) · doi:10.1109/infcom.2000.832534 · Cited by 687
Stochastic models for the Web graph
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., & Upfal, E. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892065 · Cited by 676
Modeling the Internet's large-scale topology
Yook, S.-H., Jeong, H., & Barabási, A.-L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.172501399 · Cited by 665
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
The Diameter of a Scale-Free Random Graph
Bollob�s*, B., & Riordan, O. (2004) · Combinatorica · doi:10.1007/s00493-004-0002-2 · Cited by 594
The application of network analysis to criminal intelligence: An assessment of the prospects
Sparrow, M. K. (1991) · Social Networks · doi:10.1016/0378-8733(91)90008-h · Cited by 564
Epidemic spreading in correlated complex networks
Boguñá, M., & Pastor-Satorras, R. (2002) · Physical Review E · doi:10.1103/physreve.66.047104 · Cited by 559
Highly optimized tolerance: A mechanism for power laws in designed systems
Carlson, J. M., & Doyle, J. (1999) · Physical Review E · doi:10.1103/physreve.60.1412 · Cited by 549
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2002) · Physical Review E · doi:10.1103/physreve.65.066122 · Cited by 540
Džeroski, S. (2006) · Data Mining and Knowledge Discovery Handbook · doi:10.1007/0-387-25465-x_41 · Cited by 520
On distinguishing between Internet power law topology generators
Bu, T., & Towsley, D. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019309 · Cited by 516
Problems with fitting to the power-law distribution
Goldstein, M. L., Morris, S. A., & Yen, G. G. (2004) · The European Physical Journal B · doi:10.1140/epjb/e2004-00316-5 · Cited by 495
Winners don't take all: Characterizing the competition for links on the web
Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., & Giles, C. L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.032085699 · Cited by 455
Finding communities in linear time: a physics approach
Wu, F., & Huberman, B. A. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00125-x · Cited by 451
The origin of power laws in Internet topologies revisited
Chen, Q., Chang, H., Govindan, R., & Jamin, S. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019306 · Cited by 430
Email as Spectroscopy: Automated Discovery of Community Structure within Organizations
Tyler, J. R., Wilkinson, D. M., & Huberman, B. A. (2003) · Communities and Technologies · doi:10.1007/978-94-017-0115-0_5 · Cited by 425
On the origin of power laws in Internet topologies
Medina, A., Matta, I., & Byers, J. (2000) · ACM SIGCOMM Computer Communication Review · doi:10.1145/505680.505683 · Cited by 406
Large-Scale Sparse Singular Value Computations
Berry, M. W. (1992) · The International Journal of Supercomputing Applications · doi:10.1177/109434209200600103 · Cited by 402
Spectral partitioning works: planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (1996) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548468 · Cited by 393
Small-World Phenomena and the Dynamics of Information
Kleinberg, J. (2002) · Advances in Neural Information Processing Systems 14 · doi:10.7551/mitpress/1120.003.0060 · Cited by 382
Classification of scale-free networks
Goh, K.-I., Oh, E., Jeong, H., Kahng, B., & Kim, D. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.202301299 · Cited by 377
Network topology generators: degree-based vs. structural
Tangmunarunkit, H., Govindan, R., Jamin, S., Shenker, S., & Willinger, W. (2002) · Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/633025.633040 · Cited by 375
On clusterings-good, bad and spectral
Kannan, R., Vempala, S., & Veta, A. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892125 · Cited by 372
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
Leskovec, J., Chakrabarti, D., Kleinberg, J., & Faloutsos, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11564126_17 · Cited by 356
Self-citationCooper, C., & Frieze, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10084 · Cited by 344
Multilevel Algorithms for Multi-Constraint Graph Partitioning
Karypis, G., & Kumar, V. (1998) · doi:10.5555/509058.509086 · Cited by 342
Evolution of Networks: From Biological Nets to the Internet and WWWPreprint
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · RePEc: Research Papers in Economics · Cited by 330
Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet
Fabrikant, A., Koutsoupias, E., & Papadimitriou, C. H. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45465-9_11 · Cited by 325
Experiments on Graph Clustering Algorithms
Brandes, U., Gaertler, M., & Wagner, D. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39658-1_52 · Cited by 317
Discovery of frequent DATALOG patterns
Dehaspe, L., & Toivonen, H. (1999) · Data Mining and Knowledge Discovery · doi:10.1023/a:1009863704807 · Cited by 313
(2001) · Springer eBooks · doi:10.1007/978-3-662-04599-2 · Cited by 313
Giant strongly connected component of directed networks
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2001) · Physical Review E · doi:10.1103/physreve.64.025101 · Cited by 303
Bollobás, B., Borgs, C., Chayes, J., & Riordan, O. M. (2003) · doi:10.5555/644108.644133 · Cited by 302
ANF: a fast and scalable tool for data mining in massive graphs
Palmer, C. R., Gibbons, P. B., & Faloutsos, C. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775059 · Cited by 266
Self-citationDetecting Stable Clusters Using Principal Component Analysis
Ben-Hur, A., & Guyon, I. (2003) · Functional Genomics · doi:10.1385/1-59259-364-x:159 · Cited by 252
Fully automatic cross-associations
Chakrabarti, D., Papadimitriou, S., Modha, D. S., & Faloutsos, C. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014064 · Cited by 241
Self-citationExtracting Large-Scale Knowledge Bases from the Web
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Cited by 239
Accelerated focused crawling through online relevance feedback
Chakrabarti, S., Punera, K., & Subramanyam, M. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511466 · Cited by 232
Estimating a tail exponent by modelling departure from a Pareto distribution
Feuerverger, A., & Hall, P. A. (1999) · The Annals of Statistics · doi:10.1214/aos/1018031215 · Cited by 229
Spatial gossip and resource location protocols
Kempe, D., Kleinberg, J., & Demers, A. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380796 · Cited by 224
Dězeroski, S. (2001) · Springer eBooks · Cited by 223
Discovering shared interests using graph analysis
Schwartz, M. F., & Wood, D. C. M. (1993) · Communications of the ACM · doi:10.1145/163381.163402 · Cited by 218
The reversal small-world experiment
Killworth, P. D., & Bernard, H. R. (1978) · Social Networks · doi:10.1016/0378-8733(78)90018-7 · Cited by 215
Generating network topologies that obey power laws
Palmer, C. R., & Steffan, J. G. (2002) · IEEE Global Telecommunications Conference (GLOBECOM) · doi:10.1109/glocom.2000.892042 · Cited by 209
Spectral partitioning works: Planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.07.020 · Cited by 209
Dill, S., Kumar, R., Mccurley, K. S., Rajagopalan, S., Sivakumar, D., & Tomkins, A. (2002) · ACM Transactions on Internet Technology · doi:10.1145/572326.572328 · Cited by 197
Evolution of Networks: From Biological Nets to the Internet and WWW (Physics)
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · Oxford University Press eBooks · Cited by 190
AutoPart: Parameter-Free Graph Partitioning and Outlier Detection
Chakrabarti, D. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30116-5_13 · Cited by 180
Self-citationMihail, M., & Papadimitriou, C. H. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45726-7_20 · Cited by 168
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164
The Key Player ProblemPreprint
Borgatti, S. P. (2008) · SSRN Electronic Journal · doi:10.2139/ssrn.1149843 · Cited by 147
Adamic, L. A., & Huberman, B. A. (2001) · Communications of the ACM · doi:10.1145/383694.383707 · Cited by 141
Identifying Web browsing trends and patterns
Montgomery, A. L., & Faloutsos, C. (2001) · Computer · doi:10.1109/2.933515 · Cited by 135
Self-citationThe class of all regular equivalences: Algebraic structure and computation
Borgatti, S. P., & Everett, M. G. (1989) · Social Networks · doi:10.1016/0378-8733(89)90018-x · Cited by 135
Estimating the Heavy Tail Index from Scaling Properties
Crovella, M. E., & Taqqu, M. S. (1999) · Methodology And Computing In Applied Probability · doi:10.1023/a:1010012224103 · Cited by 133
A simple conceptual model for the Internet topology
Tauro, S. L., Palmer, C., Siganos, G., & Faloutsos, M. (2002) · Globecom · doi:10.1109/glocom.2001.965863 · Cited by 127
Social Networks of Drug Users in High-Risk Sites: Finding the Connections
Weeks, M. R., Clair, S., Borgatti, S. P., Radda, K. E., & Schensul, J. J. (2002) · AIDS and Behavior · doi:10.1023/a:1015457400897 · Cited by 123
The "DGX" distribution for mining massive, skewed data
Bi, Z., Faloutsos, C., & Korn, F. R. (2001) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502521 · Cited by 118
Self-citationPower Laws, Highly Optimized Tolerance, and Generalized Source Coding
Doyle, J. C., & Carlson, J. M. (2000) · Physical Review Letters · doi:10.1103/physrevlett.84.5656 · Cited by 118
Cooper, C., & FRIEZE, A. M. (2004) · Combinatorics Probability Computing · doi:10.1017/s096354830400611x · Cited by 89
Optimal Design, Robustness, and Risk Aversion
Newman, M. E. J., Girvan, M., & Farmer, J. D. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.028301 · Cited by 73
Dill, S. J., Kumar, R., McCurley, K. S., et al. (2001) · Cited by 63
Spectral techniques in graph algorithms
Alon, N. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054322 · Cited by 57
Competition-Induced Preferential Attachment
Berger, N., Borgs, C., Chayes, J., D’Souza, R. M., & Kleinberg, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27836-8_20 · Cited by 47
Exploring the community structure of newsgroups
Borgs, C., Chayes, J., Mahdian, M., & Saberi, A. (2004) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1014052.1016914 · Cited by 43
Discovering frequent geometric subgraphs
Kuramochi, M., & Karypis, G. (2007) · Information Systems · doi:10.1016/j.is.2005.05.005 · Cited by 39
Degree Distribution of Competition-Induced Preferential Attachment Graphs
BERGER, N., Borgs, C., Chayes, J., D’Souza, R. M., & Kleinberg, R. (2005) · Combinatorics Probability Computing · doi:10.1017/s0963548305006930 · Cited by 27
Identifying Predictive Structures in Relational Data Using Multiple Instance Learning
McGovern, A., & Jensen, D. D. (2003) · Defense Technical Information Center (DTIC) · doi:10.21236/ada465314 · Cited by 26
Cited by
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Self-citationLeskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Relational learning via latent social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557109 · Cited by 799
“In large scale social networks, scale free property [3] is commonly observed.”
Background
Metadata
- Authors
- Chakrabarti, D., & Faloutsos, C.
- Venue
- ACM Computing Surveys
- Published
- 2006-06-29
- Volume
- 38
- Issue
- 1
- Pages
- 2
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2085761620
- Cited by
- 609
- References
- 165
- FWCI
- 18.91
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.