Font Size:
Maximum Entropy Triangle Model
##manager.scheduler.building##: Edificio Santa Maria
##manager.scheduler.room##: Auditorio San Agustin
Date: 2019-07-10 12:00 PM – 03:45 PM
Last modified: 2019-06-14
Abstract
We introduce and analyse a maximum entropy ensemble of random graphs with a tuneable number of triangles (tuneable clustering). This ensemble has a hard constraint on the degree distribution, and a soft constraint on the number of triangles, and it hence becomes an exponential distribution with a control parameter α for the number of triangles, defined only over those graphs that exhibit a degree sequence sampled form the imposed degree distribution.
We present the edge swap dynamics, with nontrivial move acceptance probabilities, that allows us to sample correctly from this distribution numerically. Through extensive numerical simulations, we characterise the behavior of the ensemble for four different degree distributions. Two main phases are found: a connected phase at low clustering levels, where the desired number of triangles is realised by embedding them inside the giant component, and a disconnected phase for higher clustering levels, where the desired number of triangles is realised via disconnected cliques, increasing the number of graph components and reducing the size of the giant component. Numerical simulations show that the transition between these two phases depends on the size of the graph. This dependence is such that it is impossible to have a connected clustered phase in the asymptotic limit of infinitely large graphs for any scaling of α.
Our observations are supported by analytic calculations and bounds, including estimates of the location of the transition point and an analytic formula for the degree of clustering in the connected phase, which all show excellent agreement with simulations. Our analyses result in a graph model with tuneable clustering, with potentially useful applications in the field of complex networks. For the particular case of regular graphs, much more can be done analytically. We present very accurate estimates for the number of triangles for all possible values of α. By using the replica method with imaginary limits, we finally derive an explicit formula for the average eigenvalue density of adjacency matrices in the connected phase. Also this formula shows very good agreement with simulations.
We present the edge swap dynamics, with nontrivial move acceptance probabilities, that allows us to sample correctly from this distribution numerically. Through extensive numerical simulations, we characterise the behavior of the ensemble for four different degree distributions. Two main phases are found: a connected phase at low clustering levels, where the desired number of triangles is realised by embedding them inside the giant component, and a disconnected phase for higher clustering levels, where the desired number of triangles is realised via disconnected cliques, increasing the number of graph components and reducing the size of the giant component. Numerical simulations show that the transition between these two phases depends on the size of the graph. This dependence is such that it is impossible to have a connected clustered phase in the asymptotic limit of infinitely large graphs for any scaling of α.
Our observations are supported by analytic calculations and bounds, including estimates of the location of the transition point and an analytic formula for the degree of clustering in the connected phase, which all show excellent agreement with simulations. Our analyses result in a graph model with tuneable clustering, with potentially useful applications in the field of complex networks. For the particular case of regular graphs, much more can be done analytically. We present very accurate estimates for the number of triangles for all possible values of α. By using the replica method with imaginary limits, we finally derive an explicit formula for the average eigenvalue density of adjacency matrices in the connected phase. Also this formula shows very good agreement with simulations.