Structural Transitions in Densifying Networks.

We introduce a minimal generative model for densifying networks in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability p. The networks that emerge from this copying mechanism are sparse for p<1/2 and dense (average degree increasing with number of nodes N) for p≥1/2. The behavior in the dense regime is especially rich; for example, individual network realizations that are built by copying are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at p=2/3, 3/4, 4/5, etc., where the N dependences of the number of triangles (3-cliques), 4-cliques, undergo phase transitions. When linking to second neighbors of the target can occur, the probability that the resulting graph is complete-all nodes are connected-is nonzero as N→∞.

Densification and structural transitions in networks that grow by node copying.

We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability p. When p<1/2, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in p. In the sparse regime, the network is "normal," e.g., the relative fluctuations in the number of links are asymptotically negligible. For p≥1/2, the emergent networks are dense (the average degree increases with the number of nodes N), and they exhibit intriguing structural behaviors. In particular, the N dependence of the number of m cliques (complete subgraphs of m nodes) undergoes m-1 transitions from normal to progressively more anomalous behavior at an m-dependent critical values of p. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as N^{2} as N→∞, so that the network is effectively complete as N→∞.

Ranking and clustering of nodes in networks with smart teleportation.

Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering.

Flow graphs: interweaving dynamics and structure.

The behavior of complex systems is determined not only by the topological organization of their interconnections but also by the dynamical processes taking place among their constituents. A faithful modeling of the dynamics is essential because different dynamical processes may be affected very differently by network topology. A full characterization of such systems thus requires a formalization that encompasses both aspects simultaneously, rather than relying only on the topological adjacency matrix. To achieve this, we introduce the concept of flow graphs, namely weighted networks where dynamical flows are embedded into the link weights. Flow graphs provide an integrated representation of the structure and dynamics of the system, which can then be analyzed with standard tools from network theory. Conversely, a structural network feature of our choice can also be used as the basis for the construction of a flow graph that will then encompass a dynamics biased by such a feature. We illustrate the ideas by focusing on the mathematical properties of generic linear processes on complex networks that can be represented as biased random walks and their dual consensus dynamics, and show how our framework improves our understanding of these processes.

Line graphs, link partitions, and overlapping communities.

In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm that produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this.

Role of second trials in cascades of information over networks.

We study the propagation of information in social networks. To do so, we focus on a cascade model where nodes are infected with probability p_{1} after their first contact with the information and with probability p_{2} at all subsequent contacts. The diffusion starts from one random node and leads to a cascade of infection. It is shown that first and subsequent trials play different roles in the propagation and that the size of the cascade depends in a nontrivial way on p_{1} , p_{2} , and on the network structure. Second trials are shown to amplify the propagation in dense parts of the network while first trials are dominant for the exploration of new parts of the network and launching new seeds of infection.

Majority model on a network with communities.

We focus on the majority model in a topology consisting of two coupled fully connected networks, thereby mimicking the existence of communities in social networks. We show that a transition takes place at a value of the interconnectivity parameter. Above this value, only symmetric solutions prevail, where both communities agree with each other and reach consensus. Below this value, in contrast, the communities can reach opposite opinions and an asymmetric state is attained. The importance of the interface between the subnetworks is shown.

Brownian particle having a fluctuating mass.

We focus on the dynamics of a Brownian particle whose mass fluctuates. First we show that the behavior is similar to that of a Brownian particle moving in a fluctuating medium, as studied by Beck [Phys. Rev. Lett. 87, 180601 (2001)]. By performing numerical simulations of the Langevin equation, we check the theoretical predictions derived in the adiabatic limit, i.e. when the mass fluctuation time scale is much larger than the time for reaching the local equilibrium, and study deviations outside this limit. We compare the mass velocity distribution with truncated Tsallis distributions [J. Stat. Phys. 52, 479 (1988)] and find excellent agreement if the masses are chi-squared distributed. We also consider the diffusion of the Brownian particle by studying a Bernoulli random walk with fluctuating walk length in one dimension. We observe the time dependence of the position distribution kurtosis and find interesting behaviors. We point out a few physical cases, where the mass fluctuation problem could be encountered as a first approximation for agglomeration-fracture nonequilibrium processes.

Uncovering collective listening habits and music genres in bipartite networks.

In this paper, we analyze web-downloaded data on people sharing their music library, that we use as their individual musical signatures. The system is represented by a bipartite network, nodes being the music groups and the listeners. Music groups' audience size behaves like a power law, but the individual music library size is an exponential with deviations at small values. In order to extract structures from the network, we focus on correlation matrices, that we filter by removing the least correlated links. This percolation idea-based method reveals the emergence of social communities and music genres, that are visualized by a branching representation. Evidence of collective listening habits that do not fit the neat usual genres defined by the music industry indicates an alternative way of classifying listeners and music groups. The structure of the network is also studied by a more refined method, based upon a random walk exploration of its properties. Finally, a personal identification-community imitation model for growing bipartite networks is outlined, following Potts ingredients. Simulation results do reproduce quite well the empirical data.

N-body decomposition of bipartite author networks.

In this paper, we present a method to project co-authorship networks, that accounts in detail for the geometrical structure of scientists' collaborations. By restricting the scope to three-body interactions, we focus on the number of triangles in the system, and show the importance of multi-scientist (more than two) collaborations in the social network. This motivates the introduction of generalized networks, where basic connections are not binary, but involve arbitrary number of components. We focus on the three-body case and study numerically the percolation transition.