A Family of Algorithms for Computing Consensus about Node State from Network Data

Biological and social networks are composed of heterogeneous nodes that contribute differentially to network structure and function. A number of algorithms have been developed to measure this variation. These algorithms have proven useful for applications that require assigning scores to individual nodes–from ranking websites to determining critical species in ecosystems–yet the mechanistic basis for why they produce good rankings remains poorly understood. We show that a unifying property of these algorithms is that they quantify consensus in the network about a node's state or capacity to perform a function. The algorithms capture consensus by either taking into account the number of a target node's direct connections, and, when the edges are weighted, the uniformity of its weighted in-degree distribution (breadth), or by measuring net flow into a target node (depth). Using data from communication, social, and biological networks we find that that how an algorithm measures consensus–through breadth or depth– impacts its ability to correctly score nodes. We also observe variation in sensitivity to source biases in interaction/adjacency matrices: errors arising from systematic error at the node level or direct manipulation of network connectivity by nodes. Our results indicate that the breadth algorithms, which are derived from information theory, correctly score nodes (assessed using independent data) and are robust to errors. However, in cases where nodes “form opinions” about other nodes using indirect information, like reputation, depth algorithms, like Eigenvector Centrality, are required. One caveat is that Eigenvector Centrality is not robust to error unless the network is transitive or assortative. In these cases the network structure allows the depth algorithms to effectively capture breadth as well as depth. Finally, we discuss the algorithms' cognitive and computational demands. This is an important consideration in systems in which individuals use the collective opinions of others to make decisions.Author Summary: Decision making in complex societies requires that individuals be aware of the group's collective opinions about themselves and their peers. In previous work, social power, defined as the consensus about an individual's ability to win fights, was shown to affect decisions about conflict intervention. We develop methods for measuring the consensus in a group about individuals' states, and extend our analyses to genetic and cultural networks. Our results indicate that breadth algorithms, which measure consensus by taking into account the number and uniformity of an individual's direct connections, correctly predict an individual's function even when some of the group members have erred in their assessments. However, in cases where nodes “form opinions” about other nodes using indirect information algorithms that measure the depth of consensus, like Eigenvector Centrality, are required. One caveat is that Eigenvector Centrality is not robust to error unless the network is transitive or assortative. We also discuss the algorithms' cognitive and computational demands. These are important considerations in systems in which individuals use the collective opinions of others to make decisions. Finally, we discuss the implications for the emergence of social structure.