Abstract
First-principle network models are crucial to understanding the intricate topology of real complex networks. Although modelling efforts have been quite successful in undirected networks, generative models for networks with asymmetric interactions are still not well developed and unable to reproduce several basic topological properties. Progress in this direction is of particular interest, as real directed networks are the norm rather than the exception in many natural and human-made complex systems. Here we show how the network geometry paradigm can be extended to the case of directed networks. We define a maximum entropy ensemble of random geometric directed graphs with a given sequence of in-degrees and out-degrees. Beyond these local properties, the ensemble requires only two additional parameters to fix the levels of reciprocity and the frequency of the seven possible types of three-node cycles in directed networks. A systematic comparison with several representative empirical datasets shows that fixing the level of reciprocity alongside the coupling with an underlying geometry is able to reproduce the wide diversity of clustering patterns observed in real directed complex networks.
Similar content being viewed by others
Data availability
The network datasets used in the article have been made publicly available by the original authors and were downloaded from the Netzschleuder network catalogue and repository (https://networks.skewed.de).
Code availability
The scripts and the source code of the programs used to produce the figures are publicly available on Zenodo (https://doi.org/10.5281/zenodo.8264693).
References
Boguñá, M. et al. Network geometry. Nat. Rev. Phys. 3, 114–135 (2021).
Serrano, M. Á., Krioukov, D. & Boguñá, M. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 100, 078701 (2008).
García-Pérez, G., Boguñá, M. & Serrano, M. Á. Multiscale unfolding of real networks by geometric renormalization. Nat. Phys. 14, 583–589 (2018).
Zheng, M., García-Pérez, G., Boguñá, M. & Serrano, M. Á. Scaling up real networks by geometric branching growth. Proc. Natl Acad. Sci. USA 118, e2018994118 (2021).
Boguñá, M., Krioukov, D., Almagro, P. & Serrano, M. Á. Small worlds and clustering in spatial networks. Phys. Rev. Res. 2, 023040 (2020).
Papadopoulos, F., Kitsak, M., Serrano, M. Á., Boguñá, M. & Krioukov, D. Popularity versus similarity in growing networks. Nature 489, 537–540 (2012).
Allard, A., Serrano, M. Á., García-Pérez, G. & Boguñá, M. The geometric nature of weights in real complex networks. Nat. Commun. 8, 14103 (2017).
Kleineberg, K.-K., Boguñá, M., Serrano, M. Á. & Papadopoulos, F. Hidden geometric correlations in real multiplex networks. Nat. Phys. 12, 1076–1081 (2016).
Newman, M. E. J. Networks (Oxford Univ. Press, 2018).
Allard, A., Hébert-Dufresne, L., Young, J.-G. & Dubé, L. J. General and exact approach to percolation on random graphs. Phys. Rev. E 92, 062807 (2015).
Gleeson, J. P. & Melnik, S. Analytical results for bond percolation and k-core sizes on clustered networks. Phys. Rev. E 80, 046121 (2009).
Newman, M. E. J. Properties of highly clustered networks. Phys. Rev. E 68, 026121 (2003).
Karrer, B. & Newman, M. E. J. Random graphs containing arbitrary distributions of subgraphs. Phys. Rev. E 82, 066118 (2010).
Miller, J. C. Percolation and epidemics in random clustered networks. Phys. Rev. E 80, 020901 (2009).
Battiston, F. et al. Networks beyond pairwise interactions: structure and dynamics. Phys. Rep. 874, 1–92 (2020).
Lee, C. & Wilkinson, D. J. A review of stochastic block models and extensions for graph clustering. Appl. Netw. Sci. 4, 122 (2019).
Orsini, C. et al. Quantifying randomness in real networks. Nat. Commun. 6, 8627 (2015).
Serrano, M. Á. & Boguñá, M. Tuning clustering in random networks with arbitrary degree distributions. Phys. Rev. E 72, 036133 (2005).
Volz, E. Random networks with tunable degree distribution and clustering. Phys. Rev. E 70, 056115 (2004).
Asllani, M., Lambiotte, R. & Carletti, T. Structure and dynamical behavior of non-normal networks. Sci. Adv. 4, eaau9403 (2018).
Johnson, S. Digraphs are different: why directionality matters in complex systems. J. Phys. Complex 1, 015003 (2020).
Levine, S. Several measures of trophic structure applicable to complex food webs. J. Theor. Biol. 83, 195–207 (1980).
Duan, C., Nishikawa, T., Eroglu, D. & Motter, A. E. Network structural origin of instabilities in large complex systems. Sci. Adv. 8, eabm8310 (2022).
Johnson, S., Domínguez-García, V., Donetti, L. & Muñoz, M. A. Trophic coherence determines food-web stability. Proc. Natl Acad. Sci. USA 111, 17923–17928 (2014).
Johnson, S. & Jones, N. S. Looplessness in networks is linked to trophic coherence. Proc. Natl Acad. Sci. USA 114, 5618–5623 (2017).
Klaise, J. & Johnson, S. From neurons to epidemics: How trophic coherence affects spreading processes. Chaos 26, 065310 (2016).
Nicolaou, Z. G., Nishikawa, T., Nicholson, S. B., Green, J. R. & Motter, A. E. Non-normality and non-monotonic dynamics in complex reaction networks. Phys. Rev. Res. 2, 043059 (2020).
Qu, B., Li, Q., Havlin, S., Stanley, H. E. & Wang, H. Nonconsensus opinion model on directed networks. Phys. Rev. E 90, 052811 (2014).
Shao, J., Havlin, S. & Stanley, H. E. Dynamic opinion model and invasion percolation. Phys. Rev. Lett. 103, 018701 (2009).
Michel, J., Reddy, S., Shah, R., Silwal, S. & Movassagh, R. Directed random geometric graphs. J. Complex Netw. 7, 792–816 (2019).
Wolf, F., Kirsch, C. & Donner, R. V. Edge directionality properties in complex spherical networks. Phys. Rev. E 99, 012301 (2019).
Wu, Z., Di, Z. & Fan, Y. An asymmetric popularity-similarity optimization method for embedding directed networks into hyperbolic space. Complexity 2020, 8372928 (2020).
Kovács, B. & Palla, G. Model-independent embedding of directed networks into Euclidean and hyperbolic spaces. Commun. Phys. 6, 28 (2023).
Peralta-Martinez, K. & Méndez-Bermúdez, J. A. Directed random geometric graphs: structural and spectral properties. J. Phys. Complex. 4, 015002 (2022).
Wasserman, S. & Faust, K. Social Network Analysis: Methods and Applications (Cambridge Univ. Press, 1994).
Garlaschelli, D. & Loffredo, M. I. Patterns of link reciprocity in directed networks. Phys. Rev. Lett. 93, 268701 (2004).
García-Pérez, G., Serrano, M. Á. & Boguñá, M. Soft communities in similarity space. J. Stat. Phys. 173, 775–782 (2018).
Muscoloni, A. & Cannistraci, C. V. A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities. New J. Phys. 20, 052002 (2018).
Désy, B., Desrosiers, P. & Allard, A. Dimension matters when modeling network communities in hyperbolic spaces. PNAS Nexus 2, pgad136 (2023).
Holland, P. W. & Leinhardt, S. An exponential family of probability distributions for directed graphs. J. Am. Stat. Assoc. 76, 33–50 (1981).
van der Kolk, J., Serrano, M. Á. & Boguñá, M. An anomalous topological phase transition in spatial random graphs. Commun. Phys. 5, 245 (2022).
García-Pérez, G., Allard, A., Serrano, M. Á. & Boguñá, M. Mercator: uncovering faithful hyperbolic embeddings of complex networks. New J. Phys. 21, 123033 (2019).
Coletta, L. et al. Network structure of the mouse brain connectome with voxel resolution. Sci. Adv. 6, eabb7187 (2020).
Hulse, B. K. et al. A connectome of the Drosophila central complex reveals network motifs suitable for flexible navigation and context-dependent action selection. eLife 10, e66039 (2021).
Ahnert, S. E. & Fink, T. M. A. Clustering signatures classify directed networks. Phys. Rev. E 78, 036112 (2008).
Jia, M., Gabrys, B. & Musial, K. Directed closure coefficient and its patterns. PLoS ONE 16, e0253822 (2021).
Holland, P. W. & Leinhardt, S. Local structure in social networks. Sociol. Methodol. 7, 1–45 (1976).
Bianconi, G. Entropy of network ensembles. Phys. Rev. E 79, 036114 (2009).
van der Hoorn, P., Lippner, G. & Krioukov, D. Sparse maximum-entropy random graphs with a given power-law degree distribution. J. Stat. Phys. 173, 806–844 (2018).
Chung, F. & Lu, L. Connected components in random graphs with given expected degree sequences. Ann. Comb. 6, 125–145 (2002).
Adamic, L. A. & Glance, N. The political blogosphere and the 2004 U.S. election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery 36–43 (2005).
Ryan, K., Lu, Z. & Meinertzhagen, I. A. The CNS connectome of a tadpole larva of Ciona intestinalis (L.) highlights sidedness in the brain of a chordate sibling. eLife 5, e16962 (2016).
Martinez, N. D. Artifacts or attributes? Effects of resolution on the Little Rock Lake food web. Ecol. Monogr. 61, 367–392 (1991).
De Domenico, M., Nicosia, V., Arenas, A. & Latora, V. Structural reducibility of multilayer networks. Nat. Commun. 6, 6864 (2015).
Massa, P., Salvetti, M. & Tomasoni, D. Bowling alone and trust decline in social network sites. In 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing 658–663 (2009).
Michalski, R., Palus, S. & Kazienko, P. Matching organizational structure and social network extracted from email communication. In Business Information Systems (ed. Abramowicz, W.) 197–206 (Springer, 2011).
Mastrandrea, R., Fournet, J. & Barrat, A. Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLoS ONE 10, e0136497 (2015).
Kosack, S. et al. Functional structures of US state governments. Proc. Natl Acad. Sci. USA 115, 11748–11753 (2018).
Freeman, L. C., Webster, C. M. & Kirke, D. M. Exploring social structure using dynamic three-dimensional color images. Soc. Networks 20, 109–118 (1998).
Acknowledgements
We are grateful to L. J. Dubé for comments and to the nursing staff at the Centre de recherche clinique et évaluative en oncologie (CRCEO) where part of this work was done. A.A. acknowledges financial support from the Sentinelle Nord initiative of the Canada First Research Excellence Fund and from the Natural Sciences and Engineering Research Council of Canada (project 2019-05183). M.A.S. and M.B. acknowledge support from Grant TED2021-129791B-I00 funded by MCIN/AEI/10.13039/501100011033 and the European Union NextGenerationEU/PRTR, Grant PID2022-137505NB-C22 funded by MCIN/AEI/10.13039/501100011033, Grant PID2019-106290GB-C22 funded by MCIN/AEI/10.13039/501100011033 and Generalitat de Catalunya grant number 2021SGR00856. M.B. acknowledges the ICREA Academia award funded by the Generalitat de Catalunya.
Author information
Authors and Affiliations
Contributions
All authors designed the research. A.A. and M.B. did the analytical calculations. A.A. performed the numerical simulations. All authors discussed the results and implications and wrote the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Peer review
Peer review information
Nature Physics thanks the anonymous reviewers for their contribution to the peer review of this work.
Additional information
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supplementary information
Supplementary Information
Supplementary Information Sections I–VI, Figs. 1–4 and Table I.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Allard, A., Serrano, M.Á. & Boguñá, M. Geometric description of clustering in directed networks. Nat. Phys. 20, 150–156 (2024). https://doi.org/10.1038/s41567-023-02246-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1038/s41567-023-02246-6
- Springer Nature Limited
This article is cited by
-
The D-Mercator method for the multidimensional hyperbolic embedding of real networks
Nature Communications (2023)