Modeling Dynamics of Information Networks

We propose an information-based model for network dynamics in which imperfect information leads to networks where the different vertices have widely different numbers of edges to other vertices, and where the topology has hierarchical features. The possibility to observe scale-free networks is linked to a minimally connected system where hubs remain dynamic.

Figure 1

In a perfect world, a single vertex that can differentiate all exit edges from each other might distribute all tasks and information efficiently. In real-world networks, no perfect “distributor” exists: Even when every vertex “tries” to minimize its distances to all other vertices, typical vertices tend to connect through more than one intermediate. Imperfections destabilize the central hub, and the vertices in the network obtain a wide range of vertex degrees.

Figure 2

Dynamics of edge rewiring: The edge between $i$ and $j$ is rewired to an edge between $i$ and $k$, if local information predicts that $k$ provides a shorter path to the random agent $l$ ($l=l_3$ in the figure). The agents’ information about the network is subsequently updated as shown by the shift from lower left to lower right panels. Notice that the local information is not necessarily correct.

Figure 3

Left panel: Vertex degree distribution of the evolved network with four levels of information exchange: No exchange, i.e., only rules (i) and (ii), applies in (a), full exchange as in (iii) with exchange of rate $S$ in (iv) with $S=0$, $S=0.1$, and $S=1.0$ in (b)–(d). In all lower cases, we sample dynamics of an $N=1000$ vertex system with $E=1500$ edges ($⟨C⟩=3$). The plots show averages of many samples. The upper graphs show the corresponding networks of size $N=100$. Right panel: Schematic phase diagram illustrating the critical line which separates the dynamic and nondynamic regimes. The positions of (a)–(d) are illustrated in (e) and the suggested adaptation of $⟨C⟩$ that drives the network towards a scale-free degree distribution in (f).

Figure 4

(a) Average information related to agents with vertex degree $C$ for a simulation with critical information exchange. The upper curve is the fraction of agents with correct information $I_{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{t}}$ about their paths to the specific agent of degree $C$. The lower curve similarly refers to the information $I_{\mathrm{o}\mathrm{f}}$ the agent with degree $C$ has about paths to other agents. (b) Trajectory for a specific agent with its vertex degree (dark shaded area), the information the system has about the agent, $I_{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{t}}$, and the information the agent has about the system, $I_{\mathrm{o}\mathrm{f}}$. Time is counted as the number of rewiring updates per agent.

Figure 5

Correlation profile for an ensemble of model networks with $⟨C⟩=3$. The correlation profile measures the probability for an edge between two vertices of degree $C_0$ and $C_1$ in units of what it would be in a properly randomized network. One notices that agents with $C\sim 1$ often connect to agents with $C\sim 5$ that preferentially connect to agents with high $C$. Thus, the network exhibits hierarchical features.