Impact of centrality on cooperative processes

The solution of today's complex problems requires the grouping of task forces whose members are usually connected remotely over long physical distances and different time zones. Hence, understanding the effects of imposed communication patterns (i.e., who can communicate with whom) on group performance is important. Here we use an agent-based model to explore the influence of the betweenness centrality of the nodes on the time the group requires to find the global maxima of NK-fitness landscapes. The agents cooperate by broadcasting messages, informing on their fitness to their neighbors, and use this information to copy the more successful agents in their neighborhood. We find that for easy tasks (smooth landscapes), the topology of the communication network has no effect on the performance of the group, and that the more central nodes are the most likely to find the global maximum first. For difficult tasks (rugged landscapes), however, we find a positive correlation between the variance of the betweenness among the network nodes and the group performance. For these tasks, the performances of individual nodes are strongly influenced by the agents' dispositions to cooperate and by the particular realizations of the rugged landscapes.

Figure 1

The four network topologies with $L=16$ nodes and fixed degree $k=3$ used in the computational experiments. The darker the shade of a node, the higher its betweenness. (a) Network A is the topology that maximizes both the maximum betweenness and the betweenness variance, (b) network B maximizes the average betweenness, (c) network C is a typical random network regarding the average betweenness, and (d) network D minimizes both the maximum betweenness and the betweenness variance (see Table 2).

Figure 2

Average computational cost $\langle C\rangle$ as function of the copy propensity $p$ for the four communication patterns shown in Fig. 1 according to the convention: network A $(•)$, network B $\left(▴\right)$, network C $\left(▾\right)$, and network D $\left(\blacksquare \right)$. The upper panel shows the results for $K=0$, the middle panel for $K=3$ and the lower panel for $K=7$. The lines are guides to the eye.

Figure 3

Fraction of the searches that found the solution for a fixed computational cost $C$ for network A $(•)$, network B $\left(▴\right)$, network C $\left(▾\right)$, and network D $\left(\blacksquare \right)$. The copy propensity is $p=0.85$, and the parameters of the landscape are $N=16$ and $K=7$. The lines are guides to the eye.

Figure 4

Probability that a node with betweenness $\mathcal{B}$ in network A gets the answer first for runs with computational cost less than $C$. The convention is $\mathcal{B}=0.00317(\circ ),0.114(◃),0.422(▹)$, and $0.714(\square )$ as indicated. The copy propensity is $p=1$, and the parameters of the smooth landscape are $N=16$ and $K=0$. The lines are guides to the eye.

Figure 5

Same as Fig. 4 but for rugged landscapes with parameters $N=16$ and $K=3$. The logarithmic scale in the $x$ axis highlights the change of the networks performance hierarchy for long and short runs.

Figure 6

Probability that a node with betweenness $\mathcal{B}$ in network A gets the answer first for time-unrestricted runs as function of the copy propensity. The parameters of the rugged landscapes are $N=16$ and $K=3$. The symbols convention is the same as for Fig. 4, and the lines are guides to the eye.

Figure 7

Probability that the central node in network A gets the answer first for time-unrestricted runs as function of the copy propensity for four distinct landscape realizations. The parameters of the rugged landscapes are $N=16$ and $K=3$, and the lines are guides to the eye.