Degree-dependent intervertex separation in complex networks

Exploring community structure in biological networks with random graphs

Background

Community structure is ubiquitous in biological networks. There has been an increased interest in unraveling the community structure of biological systems as it may provide important insights into a system’s functional components and the impact of local structures on dynamics at a global scale. Choosing an appropriate community detection algorithm to identify the community structure in an empirical network can be difficult, however, as the many algorithms available are based on a variety of cost functions and are difficult to validate. Even when community structure is identified in an empirical system, disentangling the effect of community structure from other network properties such as clustering coefficient and assortativity can be a challenge.

Results

Here, we develop a generative model to produce undirected, simple, connected graphs with a specified degrees and pattern of communities, while maintaining a graph structure that is as random as possible. Additionally, we demonstrate two important applications of our model: (a) to generate networks that can be used to benchmark existing and new algorithms for detecting communities in biological networks; and (b) to generate null models to serve as random controls when investigating the impact of complex network features beyond the byproduct of degree and modularity in empirical biological networks.

Conclusion

Our model allows for the systematic study of the presence of community structure and its impact on network function and dynamics. This process is a crucial step in unraveling the functional consequences of the structural properties of biological systems and uncovering the mechanisms that drive these systems.

Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees

The determination of mean first-passage time (MFPT) for random walks in networks is a theoretical challenge, and is a topic of considerable recent interest within the physics community. In this paper, according to the known connections between MFPT, effective resistance, and the eigenvalues of graph Laplacian, we first study analytically the MFPT between all node pairs of a class of growing treelike networks, which we term deterministic uniform recursive trees (DURTs), since one of its particular cases is a deterministic version of the famous uniform recursive tree. The interesting quantity is determined exactly through the recursive relation of the Laplacian spectra obtained from the special construction of DURTs. The analytical result shows that the MFPT between all couples of nodes in DURTs varies as N ln N for large networks with node number N. Second, we study trapping on a particular network of DURTs, focusing on a special case with the immobile trap positioned at a node having largest degree. We determine exactly the average trapping time (ATT) that is defined as the average of FPT from all nodes to the trap. In contrast to the scaling of the MFPT, the leading behavior of ATT is a linear function of N. Interestingly, we show that the behavior for ATT of the trapping problem is related to the trapping location, which is in comparison with the phenomenon of trapping on fractal T-graph although both networks exhibit tree structure. Finally, we believe that the methods could open the way to exactly calculate the MFPT and ATT in a wide range of deterministic media.

Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks

The complete knowledge of Laplacian eigenvalues and eigenvectors of complex networks plays an outstanding role in understanding various dynamical processes running on them; however, determining analytically Laplacian eigenvalues and eigenvectors is a theoretical challenge. In this paper, we study the Laplacian spectra and their corresponding eigenvectors of a class of deterministically growing treelike networks. The two interesting quantities are determined through the recurrence relations derived from the structure of the networks. Beginning from the rigorous relations one can obtain the complete eigenvalues and eigenvectors for the networks of arbitrary size. The analytical method opens the way to analytically compute the eigenvalues and eigenvectors of some other deterministic networks, making it possible to accurately calculate their spectral characteristics.

Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks

Various real-life networks exhibit degree correlations and heterogeneous structure, with the latter being characterized by power-law degree distribution P ( k ) ∼ k - γ , where the degree exponent γ describes the extent of heterogeneity. In this paper, we study analytically the average path length (APL) of and random walks (RWs) on a family of deterministic networks, recursive scale-free trees (RSFTs), with negative degree correlations and various γ ∊ ( 2 , 1 + ln   3 / ln   2 ] , with an aim to explore the impacts of structure heterogeneity on the APL and RWs. We show that the degree exponent γ has no effect on the APL d of RSFTs: In the full range of γ , d behaves as a logarithmic scaling with the number of network nodes N (i.e., d ∼ ln   N ), which is in sharp contrast to the well-known double logarithmic scaling ( d ∼ ln   ln   N ) previously obtained for uncorrelated scale-free networks with 2 ≤ γ < 3 . In addition, we present that some scaling efficiency exponents of random walks are reliant on the degree exponent γ .

Random walks on complex trees

We study the properties of random walks on complex trees. We observe that the absence of loops is reflected in physical observables showing large differences with respect to their looped counterparts. First, both the vertex discovery rate and the mean topological displacement from the origin present a considerable slowing down in the tree case. Second, the mean first passage time (MFPT) displays a logarithmic degree dependence, in contrast to the inverse degree shape exhibited in looped networks. This deviation can be ascribed to the dominance of source-target topological distance in trees. To show this, we study the distance dependence of a symmetrized MFPT and derive its logarithmic profile, obtaining good agreement with simulation results. These unique properties shed light on the recently reported anomalies observed in diffusive dynamical systems on trees.

Analytical solution of average path length for Apollonian networks

With the help of recursion relations derived from the self-similar structure, we obtain the solution of average path length, d[over ]_(t) , for Apollonian networks. In contrast to the well-known numerical result d[over ]_{t} proportional, variant(ln N_(t));(3/4) [J. S. Andrade, Jr., Phys. Rev. Lett. 94, 018702 (2005)], our rigorous solution shows that the average path length grows logarithmically as d[over ]_(t) proportional, variantln N_(t) in the infinite limit of network size N_(t) . The extensive numerical calculations completely agree with our closed-form solution.

The workshop on internet topology (wit) report

Internet topology analysis has recently experienced a surge of interest in computer science, physics, and the mathematical sciences. However, researchers from these different disciplines tend to approach the same problem from different angles. As a result, the field of Internet topology analysis and modeling must untangle sets of inconsistent findings, conflicting claims, and contradicting statements.On May 10-12, 2006, CAIDA hosted the Workshop on Internet topology (WIT). By bringing together a group of researchers spanning the areas of computer science, physics, and the mathematical sciences, the workshop aimed to improve communication across these scientific disciplines, enable interdisciplinary cross-fertilization, identify commonalities in the different approaches, promote synergy where it exists, and utilize the richness that results from exploring similar problems from multiple perspectives.This report describes the findings of the workshop, outlines a set of relevant open research problems identified by participants, and concludes with recommendations that can benefit all scientific communities interested in Internet topology research.