Modeling Transitivity in Complex Networks

Morteza Haghir Chehreghani Xerox Research Centre Europe, Mostafa Haghir Chehreghani KU Leuven
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:752-761, 2016.

Abstract

An important source of high clustering coefficient in real-world networks is transitivity. However, existing algorithms which model transitivity suffer from at least one of the following problems: i) they produce graphs of a specific class like bipartite graphs, ii) they do not give an analytical argument for the high clustering coefficient of the model, and iii) their clustering coefficient is still significantly lower than real-world networks. In this paper, we propose a new model for complex networks which is based on adding transitivity to scale-free models. We theoretically analyze the model and provide analytical arguments for its different properties. In particular, we calculate a lower bound on the clustering coefficient of the model which is independent of the network size, as seen in real-world networks. More than theoretical analysis, the main properties of the model are evaluated empirically and it is shown that the model can precisely simulate real-world networks from different domains with and different specifications.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-europe16a, title = {Modeling Transitivity in Complex Networks}, author = {Europe, Morteza Haghir Chehreghani Xerox Research Centre and Leuven, Mostafa Haghir Chehreghani KU}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {752--761}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/europe16a/europe16a.pdf}, url = {https://proceedings.mlr.press/r14/europe16a.html}, abstract = {An important source of high clustering coefficient in real-world networks is transitivity. However, existing algorithms which model transitivity suffer from at least one of the following problems: i) they produce graphs of a specific class like bipartite graphs, ii) they do not give an analytical argument for the high clustering coefficient of the model, and iii) their clustering coefficient is still significantly lower than real-world networks. In this paper, we propose a new model for complex networks which is based on adding transitivity to scale-free models. We theoretically analyze the model and provide analytical arguments for its different properties. In particular, we calculate a lower bound on the clustering coefficient of the model which is independent of the network size, as seen in real-world networks. More than theoretical analysis, the main properties of the model are evaluated empirically and it is shown that the model can precisely simulate real-world networks from different domains with and different specifications.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Modeling Transitivity in Complex Networks %A Morteza Haghir Chehreghani Xerox Research Centre Europe %A Mostafa Haghir Chehreghani KU Leuven %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-europe16a %I PMLR %P 752--761 %U https://proceedings.mlr.press/r14/europe16a.html %V R14 %X An important source of high clustering coefficient in real-world networks is transitivity. However, existing algorithms which model transitivity suffer from at least one of the following problems: i) they produce graphs of a specific class like bipartite graphs, ii) they do not give an analytical argument for the high clustering coefficient of the model, and iii) their clustering coefficient is still significantly lower than real-world networks. In this paper, we propose a new model for complex networks which is based on adding transitivity to scale-free models. We theoretically analyze the model and provide analytical arguments for its different properties. In particular, we calculate a lower bound on the clustering coefficient of the model which is independent of the network size, as seen in real-world networks. More than theoretical analysis, the main properties of the model are evaluated empirically and it is shown that the model can precisely simulate real-world networks from different domains with and different specifications. %Z Reissued by PMLR on 04 October 2026.
APA
Europe, M.H.C.X.R.C. & Leuven, M.H.C.K.. (2016). Modeling Transitivity in Complex Networks. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:752-761 Available from https://proceedings.mlr.press/r14/europe16a.html. Reissued by PMLR on 04 October 2026.

Related Material