The DOI matches its Crossref record; 79 of the 79 references it cites were found in a registry or an index.
Bipartite graphs as models of complex networks
Open accessAbstract
We propose here the first complex network model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some raal-world observations, and it is sufficiently simple to make it possible to prove its main properties. This model consists in sampling a random bipartite graph with prescribed degree distribution. Indeed, we show that any complex network can be viewed as a bipartite graph with some specific characteristics, and that its main properties can be viewed as consequences of this underlying structure.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
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
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
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
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
Error and attack tolerance of complex networksPreprint
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · Cited by 6,467
Bollobás, B. (1985) · Cited by 6,196
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
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
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
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
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
Spread of epidemic disease on networks
Newman, M. E. J. (2002) · Physical Review E · doi:10.1103/physreve.66.016128 · Cited by 3,218
Dorogovtsev, S. N., & Mendes, J. F. F. (2002) · Advances in Physics · doi:10.1080/00018730110112519 · Cited by 3,171
Newman, M. E. J. (2003) · Physical Review E · doi:10.1103/physreve.67.026126 · Cited by 3,087
Routing of multipoint connections
Waxman, B. M. (1988) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.12889 · Cited by 2,885
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016132 · Cited by 2,613
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
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
Resilience of the Internet to Random Breakdowns
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4626 · Cited by 2,391
A critical point for random graphs with a given degree sequence
Molloy, M., & Reed, B. (1995) · Random Structures & Algorithms · doi:10.1002/rsa.3240060204 · Cited by 2,351
Łuczak, T., Janson, S., & Ruciński, A. (2000) · Cited by 2,192
Scientific collaboration networks. I. Network construction and fundamental results
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016131 · Cited by 2,076
Cascade-based attacks on complex networks
Motter, A. E., & Lai, Y.-C. (2002) · Physical Review E · doi:10.1103/physreve.66.065102 · Cited by 1,929
Breakdown of the Internet under Intentional Attack
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3682 · Cited by 1,455
Random graph models of social networks
Newman, M. E. J., Watts, D. J., & Strogatz, S. H. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.012582999 · Cited by 1,326
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
Handbook of Combinatorial Optimization
(1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4 · Cited by 1,216
A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
Bollobás, B. (1980) · European Journal of Combinatorics · doi:10.1016/s0195-6698(80)80030-8 · Cited by 1,151
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Growing scale-free networks with tunable clustering
Holme, P., & Kim, B. J. (2002) · Physical Review E · doi:10.1103/physreve.65.026107 · Cited by 1,088
The small world of human language
Cancho, R. F. I., & Solé, R. V. (2001) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.2001.1800 · Cited by 1,046
The asymptotic number of labeled graphs with given degree sequences
Bender, E. A., & Canfield, E. R. (1978) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(78)90059-6 · Cited by 970
Epidemics and percolation in small-world networks
Moore, C., & Newman, M. E. J. (2000) · Physical Review E · doi:10.1103/physreve.61.5678 · Cited by 948
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
The Size of the Giant Component of a Random Graph with a Given Degree Sequence
MOLLOY, M., & REED, B. (1998) · Combinatorics, Probability and Computing · doi:10.1017/s0963548398003526 · Cited by 831
Scale-Free Networks Are Ultrasmall
Cohen, R., & Havlin, S. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.058701 · Cited by 815
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
Proceedings of the 30th IEEE symposium on Foundations of computer science
Galil, Z., & Blum, E. K. (1994) · Cited by 677
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
Vázquez, A. (2003) · Physical Review E · doi:10.1103/physreve.67.056104 · Cited by 563
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
A quantitative comparison of graph-based models for Internet topology
Zegura, E. W., Calvert, K. L., & Donahoo, M. J. (1997) · IEEE/ACM Transactions on Networking · doi:10.1109/90.650138 · Cited by 482
Modeling of Protein Interaction Networks
Vázquez, A., Flammini, A., Maritan, A., & Vespignani, A. (2003) · Complexus · doi:10.1159/000067642 · Cited by 472
Deterministic scale-free networks
Barabási, A.-L., Ravasz, E., & Vicsek, T. (2001) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(01)00369-7 · Cited by 464
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
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
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.503 · Cited by 345
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 310
On the uniform generation of random graphs with prescribed degree sequences
Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J., & Alon, U. (2003) · arXiv · doi:10.48550/arxiv.cond-mat/0312028 · Cited by 281
Contentment in graph theory: Covering graphs with cliques
Orlin, J. (1977) · Indagationes Mathematicae (Proceedings) · doi:10.1016/1385-7258(77)90055-5 · Cited by 275
On power-law relationships of the internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.195 · Cited by 266
Epidemic Spreading in Complex Networks with Degree Correlations
Boguá, M., Pastor-Satorras, R., & Vespignani, A. (2003) · Lecture Notes in Physics · doi:10.1007/978-3-540-44943-0_8 · Cited by 263
Bipartite structure of all complex networks
Guillaume, J.-L., & Latapy, M. (2004) · Information Processing Letters · doi:10.1016/j.ipl.2004.03.007 · Cited by 255
Self-citationEpidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignanj, A. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.493 · Cited by 245
Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence
Viger, F., & Latapy, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11533719_45 · Cited by 228
Self-citationDiameter of the world-wide web
Albert, R., Jeong, H., & Barabási, A.-L. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.182 · Cited by 223
On maximum clique problems in very large graphs
Abello, J., Pardalos, P., & Resende, M. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/06 · Cited by 221
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.349 · Cited by 221
Walsh, T. (1999) · Cited by 217
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.269 · Cited by 188
Path finding strategies in scale-free networks
Kim, B. J., Yoon, C. N., Han, S. K., & Jeong, H. (2002) · Physical Review E · doi:10.1103/physreve.65.027103 · Cited by 174
Mihail, M., & Papadimitriou, C. H. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45726-7_20 · Cited by 168
The Internet Movie Database: A Reference Guide to Hollywood and Beyond
Weible, C. L. (2001) · Internet Reference Services Quarterly · doi:10.1300/j136v06n02_05 · Cited by 161
Structural properties of scale‐free networks
Reuven Cohen, C., Havlin, S., & ben‐Avraham, D. (2002) · Wiley eBooks · doi:10.1002/3527602755.ch4 · Cited by 146
Tuning clustering in random networks with arbitrary degree distributions
Serrano, M. Á., & Boguñá, M. (2005) · Physical Review E · doi:10.1103/physreve.72.036133 · Cited by 136
A Critical Point for Random Graphs with a Given Degree Sequence
Molloy, M. S. O., & Reed, B. A. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.240 · Cited by 136
Metric structure of random networks
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2003) · Nuclear Physics B · doi:10.1016/s0550-3213(02)01119-7 · Cited by 127
Scale-Free and Hierarchical Structures in Complex Networks
Barabási, A.-Ĺ. (2003) · AIP conference proceedings · doi:10.1063/1.1571285 · Cited by 126
Network Robustness and Fragility: Percolation on Random Graphs
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., et al. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.510 · Cited by 121
Rate equation approach for correlations in growing network models
Barrat, A., & Pastor‐Satorras, R. (2005) · Physical Review E · doi:10.1103/physreve.71.036127 · Cited by 106
Exactly solvable small-world network
Dorogovtsev, S. N., & Mendes, J. F. F. (2000) · Europhysics Letters (EPL) · doi:10.1209/epl/i2000-00227-1 · Cited by 97
Competition and Adaptation in an Internet Evolution Model
Serrano, M. Á., Boguñá, M., & Díaz-Guilera, A. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.038701 · Cited by 61
(2004) · Choice Reviews Online · doi:10.5860/choice.41sup-0149 · Cited by 51
Structure of Growing Networks with Preferential Linking
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhinu, A. N. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.353 · Cited by 31
Vertex labeling and routing in recursive clique-trees, a new family of small-world scale-free graphs
Comellas, F., Guillaume Fertin, A., & André Raspaud, B. (2003) · HAL · Cited by 6
Cited by
Networks beyond pairwise interactions: Structure and dynamics
Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020) · Physics Reports · doi:10.1016/j.physrep.2020.05.004 · Cited by 1,602
Afendi, F. M., Okada, T., Yamazaki, M., Hirai-Morita, A., Nakamura, Y., Nakamura, K., Ikeda, S., Takahashi, H., Altaf-Ul-Amin, M., Darusman, L. K., et al. (2012) · Plant and Cell Physiology · doi:10.1093/pcp/pcr165 · Cited by 738
Complex network approaches to nonlinear time series analysis
Zou, Y., Donner, R. V., Marwan, N., Donges, J. F., & Kurths, J. (2019) · Physics Reports · doi:10.1016/j.physrep.2018.10.005 · Cited by 634
Basic notions for the analysis of large two-mode networks
Latapy, M., Magnien, C., & Vecchio, N. D. (2008) · Social Networks · doi:10.1016/j.socnet.2007.04.006 · Cited by 617
Self-citationPublic transport networks: empirical analysis and modeling
von Ferber, C., Holovatch, T., Holovatch, Y., & Palchykov, V. (2009) · The European Physical Journal B · doi:10.1140/epjb/e2009-00090-x · Cited by 302
Metadata
- Authors
- Guillaume, J.-L., & Latapy, M.
- Venue
- Physica A: Statistical Mechanics and its Applications
- Publisher
- Elsevier BV
- Published
- 2006-11
- Volume
- 371
- Issue
- 2
- Pages
- 795-813
- ISSN
- 0378-4371 (ISSN-L)
- OpenAlex
- W2017202214
- Cited by
- 282
- References
- 79
- FWCI
- 5.34
- Type
- journal article
- Language
- en
- Open access
- green
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.