Principles of statistical mechanics of uncorrelated random networks

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting from some critical average number of connections of a vertex, in a phase with a condensate of edges.     

Inferring topological features of proteins from amino acid residue networks

Topological properties of native folds are obtained from statistical analysis of 160 low homology proteins covering the four structural classes. This is done analyzing one, two and three-vertex joint distribution of quantities related to the corresponding network of amino acid residues. Emphasis on the amino acid residue hydrophobicity leads to the definition of their center of mass as vertices in this contact network model with interactions represented by edges. The network analysis helps us to interpret experimental results such as hydrophobic scales and fraction of buried accessible surface area in terms of the network connectivity. Moreover, those networks show assortative mixing by degree. To explore the vertex-type dependent correlations, we build a network of hydrophobic and polar vertices. This procedure presents the wiring diagram of the topological structure of globular proteins leading to the following attachment probabilities between hydrophobic–hydrophobic 0.424(5), hydrophobic-polar 0.419(2) and polar–polar 0.157(3) residues.     

Linear analysis of degree correlations in complex networks

Many real-world networks such as the protein–protein interaction networks and metabolic networks often display nontrivial correlations between degrees of vertices connected by edges. Here, we analyse the statistical methods used usually to describe the degree correlation in the networks, and analytically give linear relation in the degree correlation. It provides a simple and interesting perspective on the analysis of the degree correlation in networks, which is usefully complementary to the existing methods for degree correlation in networks. Especially, the slope in the linear relation corresponds exactly to the degree correlation coefficient in networks, meaning that it can not only characterize the level of degree correlation in networks, but also reflects the speed that the average nearest neighbours’ degree varies with the vertex degree. Finally, we applied our results to several real-world networks, validating the conclusions of the linear analysis of degree correlation. We hope that the work in this paper can be helpful for further understanding the degree correlation in complex networks.     

The Ising Partition Function for 2D Grids with Periodic Boundary: Computation and Analysis

The Ising partition function for a graph counts the number of bipartitions of the vertices with given sizes, with a given size of the induced edge cut. Expressed as a 2-variable generating function it is easily translatable into the corresponding partition function studied in statistical physics. In the current paper a comparatively efficient transfer matrix method is described for computing the generating function for the n×n grid with periodic boundary. We have applied the method to up to the 15×15 grid, in total 225 vertices. We examine the phase transition that takes place when the edge cut reaches a certain critical size. From the physical partition function we extract quantities such as magnetisation and susceptibility and study their asymptotic behaviour at the critical temperature.     

Connectivity correlations in three topological spaces of urban bus-transport networks in China

In this paper, an empirical investigation is presented, which focuses on unveiling the universality of connectivity correlations in three spaces （the route space, the stop geographical space and bus-transferring space） of urban bustransport networks （BTNs） in four major cities of China. The underlying features of the connectivity correlations are shown in two statistical ways. One is the correlation between the （weighted） average degree of all the nearest neighbouring vertices with degree k, （Knn^w,（k）） Knn（k）, and k, and the other is the correlations between the assortativity coefficient r and, respectively, the network size N, the network diameter D, the averaged clustering coefficient C, and the averaged distance （l）. The obtained results show qualitatively the same connectivity correlations of all the considered cities under all the three spaces.     

Scale-free networks via attaching to random neighbors

Preferential attachment is considered one of the key factors in the formation of scale-free networks. However, complete random attachment without a preferential mechanism can also generate scale-free networks in nature, such as protein interaction networks in cells. This article presents a new scale-free network model that applies the following general mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach to random neighbors of random vertices that are already well connected. The proposed model does not require global-based preferential strategies and utilizes only the random attachment method. Theoretical analysis and numerical simulation results denote that the proposed model has steady scale-free network characteristics, and random attachment without a preferential mechanism may generate scale-free networks.     

Dynamical robustness of networks based on betweenness against multi-node attack

We explore the robustness of a network against failures of vertices or edges where a fraction f of vertices is removed and an overload model based on betweenness is constructed. It is assumed that the load and capacity of vertex i are correlated with its betweenness centrality B_i as B_i~θ and(1 + α)Bθi(θ is the strength parameter, α is the tolerance parameter).We model the cascading failures following a local load preferential sharing rule. It is found that there exists a minimal αc when θ is between 0 and 1, and its theoretical analysis is given. The minimal αc characterizes the strongest robustness of a network against cascading failures triggered by removing a random fraction f of vertices. It is realized that the minimalαc increases with the increase of the removal fraction f or the decrease of average degree. In addition, we compare the robustness of networks whose overload models are characterized by degree and betweenness, and find that the networks based on betweenness have stronger robustness against the random removal of a fraction f of vertices.     

Dominating sets and ego–centered decompositions in social networks

Our aim here is to address the problem of decomposing a whole network into a minimal number of ego–centered subnetworks. For this purpose, the network egos are picked out as the members of a minimum dominating set of the network. However, to find such an efficient dominating ego–centered construction, we need to be able to detect all the minimum dominating sets and to compare all the corresponding dominating ego–centered decompositions of the network. To find all the minimum dominating sets of the network, we are developing a computational heuristic, which is based on the partition of the set of nodes of a graph into three subsets, the always dominant vertices, the possible dominant vertices and the never dominant vertices, when the domination number of the network is known. To compare the ensuing dominating ego–centered decompositions of the network, we are introducing a number of structural measures that count the number of nodes and links inside and across the ego–centered subnetworks. Furthermore, we are applying the techniques of graph domination and ego–centered decomposition for six empirical social networks.     

Statistical mechanics of two dimensional tilings

Reduced dimensionality in two dimensions is a topic of current interest. We use model systems to investigate the statistical mechanics of ideal networks. The tilings have possible applications such as the 2D locations of pore sites in nanoporous arrays (quantum dots), in the 2D hexagonal structure of graphene, and as adsorbates on quasicrystalline crystal surfaces. We calculate the statistical mechanics of these networks, such as the partition function, free energy, entropy, and enthalpy. The plots of these functions versus the number of links in the finite networks result in power law regression. We also determine the degree distribution, which is a combination of power law and rational function behavior. In the large-scale limit, the degree of these 2D networks approaches 3, 4, and 6, in agreement with the degree of the regular tilings. In comparison, a Penrose tiling has a degree also equal to about 4.     

Detecting community structure in networks

There has been considerable recent interest in algorithms for finding communities in networks--groups of vertices within which connections are dense, but between which connections are sparser. Here we review the progress that has been made towards this end. We begin by describing some traditional methods of community detection, such as spectral bisection, the Kernighan-Lin algorithm and hierarchical clustering based on similarity measures. None of these methods, however, is ideal for the types of real-world network data with which current research is concerned, such as Internet and web data and biological and social networks. We describe a number of more recent algorithms that appear to work well with these data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks.Received: 10 November 2003, Published online: 14 May 2004PACS: 89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems - 89.20.Hh World Wide Web, Internet - 05.10.-a Computational methods in statistical physics and nonlinear dynamics     

Mean-field Theory for Some Bus Transport Networks with Random Overlapping Clique Structure

Transport networks, such as railway networks and airport networks, are a kind of random network with complex topology. Recently, more and more scholars paid attention to various kinds of transport networks and try to explore their inherent characteristics. Here we study the exponential properties of a recently introduced Bus Transport Networks （BTNs） evolution model with random overlapping clique structure, which gives a possible explanation for the observed exponential distribution of the connectivities of some BTNs of three major cities in China. Applying mean-field theory, we analyze the BTNs model and prove that this model has the character of exponential distribution of the connectivities, and develop a method to predict the growth dynamics of the individual vertices, and use this to calculate analytically the connectivity distribution and the exponents. By comparing mean-field based theoretic results with the statistical data of real BTNs, we observe that, as a whole, both of their data show similar character of exponential distribution of the connectivities, and their exponents have same order of magnitude, which show the availability of the analytical result of this paper.     

The Linear Relationship Model with LASSO for Studying Stock Networks

The correlation-based network is a powerful tool to reveal the influential mechanisms and relations in stock markets. However, current methods for developing network models are dominantly based on the pairwise relationship of positive correlations. This work proposes a new approach for developing stock relationship networks by using the linear relationship model with LASSO to explore negative correlations under a systemic framework. The developed model not only preserves positive links with statistical significance but also includes link directions and negative correlations. We also introduce blends cliques with the balance theory to investigate the consistency properties of the developed networks. The ASX 200 stock data with 194 stocks are applied to evaluate the effectiveness of our proposed method. Results suggest that the developed networks not only are highly consistent with the correlation coefficient in terms of positive or negative correlations but also provide influence directions in stock markets.     

Operator product expansion on a fractal: The short chain expansion for polymer networks

We prove to all orders of renormalized perturbative polymer field theory the existence of a short chain expansion applying to polymer solutions of long and short chains. For a general polymer network with long and short chains we show factorization of its partition sum by a short chain factor and a long chain factor in the short chain limit. This corresponds to an expansion for short distance along the fractal perimeter of the polymer chains connecting the network vertices and is related to a large mass expansion of field theory.

The scaling of the second virial coefficient for bimodal solutions is explained. Our method also applies to the correlations of the multifractal measure of harmonic diffusion onto an absorbing polymer. We give a result for expanding these correlations for short distance along the fractal carrier of the measure.     

Mutual Voronoi tessellation in spoke pattern convection

Planar cellular networks are made of polygonal cells usually having an average of six sides and trivalent vertices. We analyze the topological properties of spoke patterns observed in the convection of highly viscous fluids. The competition between ascending and descending columns of fluid generates dual networks where on average cells are four sided and vertices tetravalent. This observation identifies a new class of dual networks satisfying a mutual Voronoi relation. The metric of the pattern is dominated by the distance between nearest neighbors vertices of opposite species.     

Ultra-small metallic grains: effect of statistical fluctuations of the chemical potential on superconducting correlations and vice versa

Superconducting correlations in an isolated metallic grain are governed by the interplay between two energy scales: the mean level spacing δ and the bulk pairing gap Δ0, which are strongly influenced by the position of the chemical potential with respect to the closest single-electron level. In turn superconducting correlations affect the position of the chemical potential. Within the parity projected BCS model we investigate the probability distribution of the chemical potential in a superconducting grain with randomly distributed single-electron levels. Taking into account statistical fluctuations of the chemical potential due to the pairing interaction, we find that such fluctuations have a significant impact on the critical level spacing δc at which the superconducting correlations cease: the critical ratio δc/Δ0 at which superconductivity disappears is found to be increased.     

A box-covering algorithm for fractal scaling in scale-free networks

A random sequential box-covering algorithm recently introduced to measure the fractal dimension in scale-free (SF) networks is investigated. The algorithm contains Monte Carlo sequential steps of choosing the position of the center of each box; thereby, vertices in preassigned boxes can divide subsequent boxes into more than one piece, but divided boxes are counted once. We find that such box-split allowance in the algorithm is a crucial ingredient necessary to obtain the fractal scaling for fractal networks; however, it is inessential for regular lattice and conventional fractal objects embedded in the Euclidean space. Next, the algorithm is viewed from the cluster-growing perspective that boxes are allowed to overlap; thereby, vertices can belong to more than one box. The number of distinct boxes a vertex belongs to is, then, distributed in a heterogeneous manner for SF fractal networks, while it is of Poisson-type for the conventional fractal objects.     

Weighted evolving networks: coupling topology and weight dynamics

We propose a model for the growth of weighted networks that couples the establishment of new edges and vertices and the weights' dynamical evolution. The model is based on a simple weight-driven dynamics and generates networks exhibiting the statistical properties observed in several real-world systems. In particular, the model yields a nontrivial time evolution of vertices' properties and scale-free behavior for the weight, strength, and degree distributions.     

A measurement of R_{\rm b} using a double tagging method

The fraction of events in hadronic decays has been measured by the OPAL experiment using the data collected at LEP between 1992 and 1995. The decays were tagged using displaced secondary vertices, and high momentum electrons and muons. Systematic uncertainties were reduced by measuring the b-tagging efficiency using a double tagging technique. Efficiency correlations between opposite hemispheres of an event are small, and are well understood through comparisons between real and simulated data samples. A value of was obtained, where the first error is statistical and the second systematic. The uncertainty on , the fraction of events in hadronic decays, is not included in the errors. The dependence on is where $\Delta R_{\rm c}$ is the deviation of from the value 0.172 predicted by the Standard Model. The result for agrees with the value of predicted by the Standard Model. Received: 28 August 1998 / Published online: 7 April 1999     

Clique percolation in random networks

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.     

Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model “Network formed by traces of random walks”, because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex–vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices.