Limited resolution in complex network community detection with Potts model approach

According to Fortunato and Barthélemy, modularity-based community detection algorithms have a resolution threshold such that small communities in a large network are invisible. Here we generalize their work and show that the q-state Potts community detection method introduced by Reichardt and Bornholdt also has a resolution threshold. The model contains a parameter by which this threshold can be tuned, but no a priori principle is known to select the proper value. Single global optimization criteria do not seem capable for detecting all communities if their size distribution is broad.     

Growing distributed networks with arbitrary degree distributions

We consider distributed networks, such as peer-to-peer networks, whose structure can be manipulated by adjusting the rules by which vertices enter and leave the network. We focus in particular on degree distributions and show that, with some mild constraints, it is possible by a suitable choice of rules to arrange for the network to have any degree distribution we desire. We also describe a mechanism based on biased random walks by which appropriate rules could be implemented in practice. As an example application, we describe and simulate the construction of a peer-to-peer network optimized to minimize search times and bandwidth requirements.     

Preservation of network degree distributions from non-uniform failures

There has been a considerable amount of interest in recent years on the robustness of networks to failures. Many previous studies have concentrated on the effects of node and edge removals on the connectivity structure of a static network; the networks are considered to be static in the sense that no compensatory measures are allowed for recovery of the original structure. Real world networks such as the world wide web, however, are not static and experience a considerable amount of turnover, where nodes and edges are both added and deleted. Considering degree-based node removals, we examine the possibility of preserving networks from these types of disruptions. We recover the original degree distribution by allowing the network to react to the attack by introducing new nodes and attaching their edges via specially tailored schemes. We focus particularly on the case of non-uniform failures, a subject that has received little attention in the context of evolving networks. Using a combination of analytical techniques and numerical simulations, we demonstrate how to preserve the exact degree distribution of the studied networks from various forms of attack.     

Developmental time windows for spatial growth generate multiple-cluster small-world networks

Many networks extent in space, may it be metric (e.g. geographic) or non-metric (ordinal). Spatial network growth, which depends on the distance between nodes, can generate a wide range of topologies from small-world to linear scale-free networks. However, networks often lacked multiple clusters or communities. Multiple clusters can be generated, however, if there are time windows during development. Time windows ensure that regions of the network develop connections at different points in time. This novel approach could generate small-world but not scale-free networks. The resulting topology depended critically on the overlap of time windows as well as on the position of pioneer nodes.     

The network of concepts in written texts

Complex network theory is used to investigate the structure of meaningful concepts in written texts of individual authors. Networks have been constructed after a two phase filtering, where words with less meaning contents are eliminated and all remaining words are set to their canonical form, without any number, gender or time flexion. Each sentence in the text is added to the network as a clique. A large number of written texts have been scrutinised, and it is found that texts have small-world as well as scale-free structures. The growth process of these networks has also been investigated, and a universal evolution of network quantifiers have been found among the set of texts written by distinct authors. Further analyses, based on shuffling procedures taken either on the texts or on the constructed networks, provide hints on the role played by the word frequency and sentence length distributions to the network structure.     

Walks on Apollonian networks

We carry out comparative studies of random walks on deterministic Apollonian networks (DANs) and random Apollonian networks (RANs). We perform computer simulations for the mean first-passage time, the average return time, the mean-square displacement, and the network coverage for the unrestricted random walk. The diffusions both on DANs and RANs are proved to be sublinear. The effects of the network structure on the dynamics and the search efficiencies of walks with various strategies are also discussed. Contrary to intuition, it is shown that the self-avoiding random walk, which has been verified as an optimal local search strategy in networks, is not the best strategy for the DANs in the large size limit.     

The backbone of a city

Recent studies have revealed the importance of centrality measures to analyze various spatial factors affecting human life in cities. Here we show how it is possible to extract the backbone of a city by deriving spanning trees based on edge betweenness and edge information. By using as sample cases the cities of Bologna and San Francisco, we show how the obtained trees are radically different from those based on edge lengths, and allow an extended comprehension of the “skeleton” of most important routes that so much affects pedestrian/vehicular flows, retail commerce vitality, land-use separation, urban crime and collective dynamical behaviours.     

Characterization of complex networks by higher order neighborhood properties

A concept of higher order neighborhood in complex networks, introduced previously [Phys. Rev. E 73, 046101 (2006)], is systematically explored to investigate larger scale structures in complex networks. The basic idea is to consider each higher order neighborhood as a network in itself, represented by a corresponding adjacency matrix, and to settle a plenty of new parameters in order to obtain a best characterization of the whole network. Usual network indices are then used to evaluate the properties of each neighborhood. The identification of high order neighborhoods is also regarded as intermediary step towards the evaluation of global network properties, like the diameter, average shortest path between node, and network fractal dimension. Results for a large number of typical networks are presented and discussed.     

Mapping dynamical systems onto complex networks

The objective of this study is to design a procedure to characterize chaotic dynamical systems, in which they are mapped onto a complex network. The nodes represent the regions of space visited by the system, while the edges represent the transitions between these regions. Parameters developed to quantify the properties of complex networks, including those related to higher order neighbourhoods, are used in the analysis. The methodology is tested on the logistic map, focusing on the onset of chaos and chaotic regimes. The corresponding networks were found to have distinct features that are associated with the particular type of dynamics that generated them.     

Large-scale structure of time evolving citation networks

In this paper we examine a number of methods for probing and understanding the large-scale structure of networks that evolve over time. We focus in particular on citation networks, networks of references between documents such as papers, patents, or court cases. We describe three different methods of analysis, one based on an expectation-maximization algorithm, one based on modularity optimization, and one based on eigenvector centrality. Using the network of citations between opinions of the United States Supreme Court as an example, we demonstrate how each of these methods can reveal significant structural divisions in the network and how, ultimately, the combination of all three can help us develop a coherent overall picture of the network's shape.     

The effect of the forget-remember mechanism on spreading

We introduce a new mechanism—the forget-remember mechanism into the spreading process. Equipped with such a mechanism an individual is prone to forget the “message" received and remember the one forgotten, namely switching his state between active (with message) and inactive (without message). The probability of state switch is governed by linear or exponential forget-remember functions of history time which is measured by the time elapsed since the most recent state change. Our extensive simulations reveal that the forget-remember mechanism has significant effects on the saturation of message spreading, and may even lead to a termination of spreading under certain conditions. This finding may shed some light on how to control the spreading of epidemics. It is found that percolation-like phase transitions can occur. By investigating the properties of clusters, formed by connected, active individuals, we may be able to justify the existence of such phase transitions.     

Rank-based model for weighted network with hierarchical organization and disassortative mixing

In this paper, we study a rank-based model for weighted network. The evolution rule of the network is based on the ranking of node strength, which couples the topological growth and the weight dynamics. Analytically and by simulations, we demonstrate that the generated networks recover the scale-free distributions of degree and strength in the whole region of the growth dynamics parameter (α>0). Moreover, this network evolution mechanism can also produce scale-free property of weight, which adds deeper comprehension of the networks growth in the presence of incomplete information. We also characterize the clustering and correlation properties of this class of networks. It is showed that at α=1 a structural phase transition occurs, and for α>1 the generated network simultaneously exhibits hierarchical organization and disassortative degree correlation, which is consistent with a wide range of biological networks.     

Inevitable self-similar topology of binary trees and their diverse hierarchical density

Self-similar topology, which can be characterized as power law size distribution, has been found in diverse tree networks ranging from river networks to taxonomic trees. In this study, we find that the statistical self-similar topology is an inevitable consequence of any full binary tree organization. We show this by coding a binary tree as a unique bifurcation string. This coding scheme allows us to investigate trees over the realm from deterministic to entirely random trees. To obtain partial random trees, partial random perturbation is added to the deterministic trees by an operator similar to that used in genetic algorithms. Our analysis shows that the hierarchical density of binary trees is more diverse than has been described in earlier studies. We find that the connectivity structure of river networks is far from strict self-similar trees. On the other hand, organization of some social networks is close to deterministic supercritical trees.     

Role of connectivity in congestion and decongestion in a communication network

We study network traffic dynamics in a two dimensional communication network with regular nodes and hubs. If the network experiences heavy message traffic, congestion occurs due to finite capacity of the nodes. We discuss strategies to manipulate hub capacity and hub connections to relieve congestion and define a coefficient of betweenness centrality (CBC), a direct measure of network traffic, which is useful for identifying hubs which are most likely to cause congestion. The addition of assortative connections to hubs of high CBC relieves congestion very efficiently. An erratum to this article is available at .     

Kinetic-growth self-avoiding walks on small-world networks

Kinetically-grown self-avoiding walks have been studied on Watts-Strogatz small-world networks, rewired from a two-dimensional square lattice. The maximum length L of this kind of walks is limited in regular lattices by an attrition effect, which gives finite values for its mean value 〈L 〉. For random networks, this mean attrition length 〈L 〉 scales as a power of the network size, and diverges in the thermodynamic limit (system size N ↦∞). For small-world networks, we find a behavior that interpolates between those corresponding to regular lattices and randon networks, for rewiring probability p ranging from 0 to 1. For p < 1, the mean self-intersection and attrition length of kinetically-grown walks are finite. For p = 1, 〈L 〉 grows with system size as N^1/2, diverging in the thermodynamic limit. In this limit and close to p = 1, the mean attrition length diverges as (1-p)^-4. Results of approximate probabilistic calculations agree well with those derived from numerical simulations.     

Neutron diffraction study of the magnetic structure of Na2 RuO 4

We present a novel model to simulate real social networks of complex interactions, based in a system of colliding particles (agents). The network is build by keeping track of the collisions and evolves in time with correlations which emerge due to the mobility of the agents. Therefore, statistical features are a consequence only of local collisions among its individual agents. Agent dynamics is realized by an event-driven algorithm of collisions where energy is gained as opposed to physical systems which have dissipation. The model reproduces empirical data from networks of sexual interactions, not previously obtained with other approaches.     

Network robustness to targeted attacks. The interplay of expansibility and degree distribution

We study the property of certain complex networks of being both sparse and highly connected, which is known as “good expansion” (GE). A network has GE properties if every subset S of nodes (up to 50% of the nodes) has a neighborhood that is larger than some “expansion factor” φ multiplied by the number of nodes in S. Using a graph spectral method we introduce here a new parameter measuring the good expansion character of a network. By means of this parameter we are able to classify 51 real-world complex networks — technological, biological, informational, biological and social — as GENs or non-GENs. Combining GE properties and node degree distribution (DD) we classify these complex networks in four different groups, which have different resilience to intentional attacks against their nodes. The simultaneous existence of GE properties and uniform degree distribution contribute significantly to the robustness in complex networks. These features appear solely in 14% of the 51 real-world networks studied here. At the other extreme we find that ∼40% of all networks are very vulnerable to targeted attacks. They lack GE properties, display skewed DD — exponential or power-law — and their topologies are changed more dramatically by targeted attacks directed at bottlenecks than by the removal of network hubs.     

On the rich-club effect in dense and weighted networks

For many complex networks present in nature only a single instance, usually of large size, is available. Any measurement made on this single instance cannot be repeated on different realizations. In order to detect significant patterns in a real-world network it is therefore crucial to compare the measured results with a null model counterpart. Here we focus on dense and weighted networks, proposing a suitable null model and studying the behaviour of the degree correlations as measured by the rich-club coefficient. Our method solves an existing problem with the randomization of dense unweighted graphs, and at the same time represents a generalization of the rich-club coefficient to weighted networks which is complementary to other recently proposed ones.     

How non-uniform tolerance parameter strategy changes the response of scale-free networks to failures

In this paper, we introduce a non-uniform tolerance parameter (TP) strategy (the tolerance parameter is characterized by the proportion between the unused capacity and the capacity of a vertex) and study how the non-uniform TP strategy influences the response of scale-free (SF) networks to cascading failures. Different from constant TP in previous work of Motter and Lai (ML), the TP in the proposed strategy scales as a power-law function of vertex degree with an exponent b. The simulations show that under low construction costs D, when b>0 the tolerance of SF networks can be greatly improved, especially at moderate values of b; When b<0 the tolerance gets worse, compared with the case of constant TP in the ML model. While for high D the tolerance declines slightly with the b, namely b<0 is helpful to the tolerance, and b>0 is harmful. Because for smaller b the cascade of the network is mainly induced by failures of most high-degree vertices; while for larger b, the cascade attributes to damage of most low-degree vertices. Furthermore, we find that the non-uniform TP strategy can cause changes of the structure and the load-degree correlation in the network after the cascade. These results might give insights for the design of both network capacity to improve network robustness under limitation of small cost, and for the design of strategies to defend cascading failures of networks.     

Dynamics of congestion transition triggered by multiple walkers on complex networks

The congestion transition triggered by multiple walkers walking along the shortest path on complex networks is numerically investigated. These networks are composed of nodes that have a finite capacity in analogy to the buffer memory of a computer. It is found that a transition from free-flow phase to congestion phase occurs at a critical walker density f_c, which varies for complex networks with different topological structures. The dynamic pictures of congestion for networks with different topological structures show that congestion on scale-free networks is a percolation process of congestion clusters, while the dynamics of congestion transition on non-scale-free networks is mainly a process of nucleation.