A Family of Algorithms for Computing Consensus about Node State from Network Data
A goal of many of network studies ( e . g . 1–4 ) is to predict the effects of perturbations , such as extinction and predation events , on network structure ., Making these predictions requires information about network connectivity ( e . g . is the network scale-free , exponential , etc . ) ., When the connectivity is non-uniform , it is also important to quantify variation at the node level in order to identify nodes that , if removed , are likely to impact negatively network stability ., This is well recognized and many useful methods have been developed for measuring this variation 1–2 , 5–14 in a range of networks , including the world-wide web 5 , food webs describing trophic interactions 1 , 2 , networks of interactions between genes and proteins 6–10 , and social networks , in both animal and human societies 11–16 ., Patterns of connectivity can also influence node function in the larger system of which the network is a part ., For example , in previous work on the behavioral causes of multi-scale social structure in primate societies 14 , 17–22 it was found that group consensus about an individuals ability to win fights – its social power ( see Sec . Primate communication network ) –is population coded in a status signaling network ., In this system , individuals use subordination signals to communicate to adversaries that they perceive themselves to be the weaker opponent ., The signals are often repeated and are always unidirectional ( emitted by one individual in a pair but not the other ) ., A single signal indicates that the sender perceives the receiver capable of using force successfully against him ., The frequency of signals emitted ( over some defined time period ) indicates the strength of the senders perception that the receiver can successfully use force against him ., In the work cited above it was demonstrated that consensus in the group about individual ability to successfully win its fights can be calculated by quantifying uniformity in the weighted in-degree distribution of signals sent to by its senders and weighting this score by the total number of signals received ( this calculation is described in Sec . Shannon consensus ) ., The resulting score for may not be the preferred score for of any specific group member , but can be said to reflect the groups collective view about how good is at winning fights ., Correspondingly , the rank order associated with the distribution of scores in the population might not match the preferred rank order of any single individual , but as the outcome of integrating over all of the individual opinions , it can be said to be the consensus social power rank order ., The data indicate that individuals can estimate their own social power and also know something about how others in the group are collectively perceived 17 , 20 , 23 , 24 ., Consequently , social power is informative about the likely cost of interaction when interactions are not strictly pair-wise ( a common feature of these systems and the reason why a consensus-based definition is important ) 17–19 ., Under heavy-tailed power distributions , in which a few individuals are disproportionately powerful , conflict management mechanisms like third-party policing ( a critical social function ) can emerge and are performed by nodes in the tail of the power distribution 14 , 20 ., Policing is an important social function because by controlling conflict it facilitates edge building by nodes in the signaling as well as other social networks 18 , 20 ., These results suggest that ( 1 ) network structure can encode node function and that ( 2 ) measures that quantify agreement in node connectivity patterns can be used to decode this population coding of node function ., In Table 1 we give several examples of other networks in which node function might also be population coded and consensus estimation could be useful for identifying important nodes ., In principle , consensus about node state or function can be quantified by measuring the uniformity of a nodes weighted in-degree distribution 14 , as in the above example , by measuring the “flow” into and out of a node ( depth ) , or using simple counts ., To capture these competing notions of consensus , we introduce a variety of alternative information theoretic , diffusion , and count algorithms that capture breadth and depth to different degrees , and so serve as hypotheses about how functional variation in nodes is encoded in interaction networks via consensus ., The algorithms take an interaction network as input and produce a vector of scores for the nodes in the network as output ., We interpret the score of node as the collective opinion , or consensus , about state or its capacity to perform a given behavior ., We note that the algorithms only quantify agreement in the connectivity patterns; what the consensus is about– state– depends on the type of interactions in the interaction network ., For example , in the work on power in primate societies mentioned above , the interaction matrix contained directed subordination signals ., These signals have special properties that allow them to reliably encode information about the ability to win fights , which is the basis of power 19 ., We discuss the importance of the interaction matrix for the interpretation of consensus in greater detail in Sec ., Background and motivation ., After introducing the algorithms , we compare their mathematical properties , and in a few cases , establish approximate equivalence ., We introduce three data sets that we use to empirically evaluate how well the output of the algorithms predicts node function out of sample ., We investigate the properties of these algorithms that make them predictive measures of consensus ., The data sets include a status communication network in a primate society , a network of collaborating condensed matter physicists from a prominent journal , and a functional linkage network of yeast genes that influence viability and growth ., Finally , we assess the sensitivity of the algorithms to systematic error at the node level and strategic manipulation of the network by nodes or small sub-sets of the network ., Here we consider one additional algorithm , the Borda count , for computing consensus on networks ., The Borda count is an algorithm that is traditionally used to determine the outcome of an election ., Each member of a voting population ranks the candidates of the election ., This is analogous to each individual in a primate group emitting signals to others in accordance with whom they perceive as more or less likely to use force successfully ., The Borda count aggregates these preferences into one ranking over the candidates ., Supposing that there are candidates , each voter gives votes to his highest preference , to his next highest choice , on down to one vote to his least favorite candidate ., A voter can rank candidates equally and the candidates votes in this case are the average of the numbers of votes they would have received were they not tied ., A candidates score is the sum of his votes from each voter ., In the signaling case , the receiver of the most signals from a given individual will receive n “votes” and the receiver of the fewest signals from that individual will receive one “vote” ., In unweighted networks , each individual “voter” divides the group into nodes with whom he does or does not interact , giving the same number of votes to the individuals in each class ., Mathematically , we define a matrix such that is the rank given node by node , where gives rank to its highest preference and rank to its lowest preference , and define the vector is the Borda consensus scores for node ., The Borda count is more coarse-grained than the total frequency of interactions received because information about the number of interactions received is lost and only the ordinal ranking of nodes by the number of interactions received is used ., It does , however , convey information about agreement among interaction partners ., If we find that a node has a high score under the Borda count , this indicates that many other nodes rank the receiver highly and agree about its relative value to them ., Hence like Shannon Consensus it should be intrinsically sensitive to certain kinds of bias in the interaction matrix ( see Sec . Empirical Comparison for further discussion ) ., All of the algorithms we compare provide some measure of consensus in a network about the state of a given node , such that we expect they are positively correlated ( these data are presented in Sec . Basics of data set ) ., In fact , we can describe these correlations by deriving mathematical relationships between some of the algorithms ., The mathematical relationships between the breadth algorithms are easiest to see ., , and are related by the definition of and a simple theorem about :Consider the definitions of and :These definitions make the mathematical relationships and on the one hand and obvious ., If the network is unweighted , then we can write the following algorithms as a function of in-degree , :where is constant across nodes and depends on the total number of edges in the network ., In this case , the rankings generated by these algorithms will be the same , although the actual values will be different ., Eigenvector Centrality can be related to the redistribution probabilities and in-degree ., Recall that is the stochastic transition matrix where denotes the probability of walking from node to node and Eigenvector Centrality is defined by the equation Since is stochastic , for all and we can choose such that ., Since , this gives If we let , then and we can show thatwhere ., In the case that for all , these bounds can be combined to giveThis bound gives an indication of how is related to the number of interactions received and the redistribution weights used in the calculation of ., As we increase the redistribution weight , the minimum possible Eigenvector Centrality scores increases ., In general , nodes that engage in more interactions and that interact with nodes with few other interaction partners will have higher Eigenvector Centrality scores ., Much of the research on consensus aims to determine how a group comes to a single decision , such as which direction to move , who should be president , etc ., 30–33 ., In this study our aim is somewhat different ., Our goal is to quantify how much consensus there is in the group ( e . g . network ) about the state of a node ( is it on or off , is it capable of performing a target function , etc . ) ., Hence the interpretation of consensus turns on the meaning of the edges in the network , represented by the data in the interaction matrix , as much as on the algorithm applied to the matrix to compute the consensus scores for the nodes ., It is therefore critical that the interaction data used to construct the matrix be chosen carefully ., Below we provide basic details about the three test systems –a primate status communication network , a collaboration network , and a functional gene linkage network ., We provide the biological interpretation of the edges in the networks and of node state , and we introduce the functional data used to empirically evaluate the algorithms performance ., We note that the mechanistic basis for consensus as an important network measurement is best understood for the primate communication network , and this fact is reflected in that sections length ., In Table 1 we provide interpretations of consensus scores for several different kinds of networks in addition to those we describe below ., We are using a primate communication network in a large captive social group of pigtailed macaques ( Macaca nemestrina ) to measure social power , operationalized as group consensus about individual ability to win fights ., We are using a collaboration network to measure reputation , defined operationally as group consensus about whether to work with a given scientist ., We are using a network of functional linkages between genes to measure gene importance , defined operationally as group consensus about whether to be functionally linked with a given gene ( this “decision” could be made in either developmental or evolutionary time ) ., Each algorithm produces as output a vector of scores for nodes in the network ., In Table S1 in Text S1 we present the correlations between these outputs for each network ., The distribution of consensus scores for each of the networks , according to each of the algorithms considered in this paper , is presented in Figures S2 , S3 and S4 ., Within each data set , most algorithms suggest roughly similar distributions ., In the case of the signaling network , these distributions look heavy-tailed , which is consistent with the distributions of functional data ., Additionally , for the signaling network , two of the algorithms– Shannon Consensus and Weighted Simple Consensus– produce distributions that are not significantly different than normal after log transform , indicating they are consistent with the log-normal distribution ., Our predictor variables are the social power indices produced by the consensus algorithms ., Dependent variables include: support solicited – requests for support received by a third-party to a fight from fight participants ( should be positively correlated with power ) ; intervention cost – operationalized as the intensity of aggression received by an intervener in response to its interventions into fights among group members ( should be negatively correlated with ) ; and intensity of aggression used by an intervener during its intervention ( should be negatively correlated ) ( these variables are defined and the data collection methods are described in Section Methods and in 14 ) ., These dependent variables are corrected for underlying variation in tendency to fight ( see Section Methods ) ., All algorithms are significantly correlated with the dependent variables ( , Table 4 ) ., The best predictor of the dependent variables is Weighted Simple Consensus , followed closely by Shannon Consensus , and Eigenvector Centrality ., The worst predictors are Davids Score , Borda Count , and Simple Consensus ., The most highly predictive algorithms have very similar values , so it is hard to differentiate between them based on their predictive power alone ., However , as we discuss below , these algorithms vary in their sensitivity to source biases and in their computational and cognitive complexity ., In this social system , there are a few individuals in the tail of the power distribution who are disproportionately powerful 14 , 17 ., This is borne out in our data , as the correlation between the algorithm scores and the dependent variables is substantially higher for the top quartiles than the bottom quartiles ( Figure 1 ) ., Our predictor variables are the reputation indices produced by the consensus algorithms ., The dependent variable is total amount of grant money awarded to a PI or CoPI by the National Science Foundation ( see Section Methods ) ., Of all the algorithms we consider , only Eigenvector Centrality is significantly correlated with this external variable ( , Table 4 ) ., Two reasons , one mathematical and one sociological , appear to account for this result ., First , Eigenvector Centrality can distinguish between nodes that have identical local neighborhoods ., In-degree can only take integer values and there is presumably an upper bound on the number of possible collaborators given time and other constraints ., In this network , the highest in-degree observed is so that there are possible values , , a nodes in-degree can take ., As Eigenvector Centrality can take any value between and , it can give different scores to nodes with the same in-degree ., In other words , Eigenvector Centrality uses global information to differentiate between nodes that are locally identical ., This effect is not as noticeable in the subordination signaling network because there are only individuals in the signaling network and therefore less degeneracy in the in-degree distribution ., Second , it is perhaps not surprising that for this kind of network Eigenvector Centrality is more predictive of the dependent variable than the breadth algorithms – although physicists involved in the process of awarding grants to others are expected to recuse themselves when confronted with an application from one of their own collaborators , they may be more likely to award grants to collaborators of their collaborators ., Therefore , having many collaborators may not be that helpful in receiving grant money , but scientists whose collaborators have many collaborators may have an advantage ., Our predictor variables are the importance indices produced by the consensus algorithms ., The dependent variables are the viability and competitive fitness of organisms with mutated versions of the gene ., For each of our algorithms , the importance scores for essential genes are significantly higher than the importance scores for non-essential genes ( , Table 4 ) ., Similarly , for each algorithm , the importance scores are significantly negatively correlated with the competitive fitness variable ( , Table 4 ) ., The most predictive algorithms are , in order , Eigenvector Centrality , Simple Consensus , the Borda count , and Shannon Consensus ., In differentiating between essential and non-essential genes , Eigenvector Centrality is marginally better than the other algorithms ., In predicting competitive fitness , the four most predictive algorithms perform equally well ., With both external variables , the test statistics are noticeably smaller for the Graph Laplacian than for the other algorithms ., As we showed above , on unweighted networks , On both the collaboration and linkage networks , nodes with high in-degree tend to interact with many other highly connected nodes ., For both networks , we find high correlations between in-degree , , and the sum of the in-degrees of a nodes neighbors , ( , , for the collaboration network and , , for the linkage network ) ., Nodes that have many interactions with other highly connected nodes receive low Graph Laplacian scores , a counterintuitive result that suggests the Graph Laplacian is not a robust measure of consensus ., We summarize the predictive performance of the algorithms on the three data sets in Table 5 ., An important question in evaluating the performance of a consensus algorithm is how sensitive the algorithm is to deficiencies in the data in the interaction matrix ., Aspects of this question have been addressed in previous work ., Ghoshal et al . 57 showed that in scale-free networks of sufficient size , if all edges in the network are shuffled but the in-degrees maintained , the ranking of the nodes according to eigenvector centrality is not severely perturbed ., This type of shuffle allows the researcher to simulate the effects of missing or noisy data in the interaction matrix on an algorithms output ., We are particularly interested in the effects on the algorithms output of nodes systematically making errors in their assessments of the states of other nodes or nodes attempting to manipulate social structure by “loading the deck” or inflating the consensus scores of nodes by , for example , manipulating the weighted degree distribution ., ( One way to manipulate the weighted degree distribution is to inflate a nodes weighted in-degree by sending many signals . ), Capturing this kind of “deficiency , ” which we call source bias requires a different kind of shuffle ., First , we measure in our interaction matrices the correlation between a nodes Shannon entropy ( as defined in Sec . Shannon consensus ) and the total frequency of interactions it receives ( weighted in-degree or in-degree ) ( see Table S1 in Text S1 ) ., If entropy and in-degree were poorly correlated , we could independently evaluate the effects of receiving many interactions from receiving interactions from many individuals ., However , this is not the case on the data sets we consider ., We break the correlation by systemically shuffling the data in the matrices such that we create matrices with strong source biases but conserve the total number of interactions ( e . g . signals ) received ., We now have two matrices –the original , unshuffled matrix , and the shuffled matrix , ., We then compute consensus scores for the nodes using the unshuffled and shuffled matrices and assess how much the rank order changes under the shuffle ., More specifically , for a given pair of interaction partners in the network , say nodes and , we construct a matrix in which the target node , receives all of its interactions from partner node , ., If the original network is directed , we hold constant the out-edges of in addition to holding constant weighted in-degree ., If the original network is undirected , we maintain the symmetry ., The subordination signaling network is small enough so that we can perform this shuffle for every pair of partners ., However , the collaboration network and the functional linkage networks are too large to exhaust every pair of partners , so we choose of the nodes that are also represented in the functional data sets ., Partner nodes are chosen at random from the target nodes neighbors ., An algorithm is said to be sensitive to source bias if the rank order of the shuffled matrix , differs from the rank order of the original matrix , ., Large changes in the rank order indicate that the test algorithm tends to give higher scores to nodes that interact with many neighbors than to nodes that interact strongly with just one other node and is an indication that the algorithm is sensitive to source biases ., We find that Shannon Consensus , and the Graph Laplacian , , tend to be quite sensitive to source biases ( Figure 2 ) ., This is expected , as and depend on the entropy of the receiving distribution , which is by design in the shuffled matrices ., By definition , in-degree , , is maximally insensitive to source bias as we hold it constant in our shuffle ., Eigenvector Centrality , , is also fairly insensitive , but the explanation why is initially counter-intuitive ., As can be seen in Figure 2 , Eigenvector Centrality appears to be particularly insensitive to the shuffle for the subordination signaling network , as the rank order for the shuffled and unshuffled matrices for that network is very similar ., The reason for this is that in the subordination signaling network individuals who receive many signals receive some of these signals from partners who themselves receive many signals ., In addition individuals who receive many signals send very few signals ., Hence there is information about breadth encoded in the second and third order connections ( and so forth ) in the network ., Even if we shuffle the matrix so that all of an individuals signals come from a single other node , as long as we hold constant the out-edges of , the in-edges to are likely to be from an individual who itself receives relatively many signals ., Eigenvector Centrality , by emphasizing paths through the network , takes these second and third order connections into account ., It is consequently likely to get the rank order right , even after we reduce the diversity or breadth in the first order or direct connections , as long as the second and third order connections in the shuffled matrices encode information about the first order connections in the unshuffled matrices ., See Text S1 , Section Sensitivity of eigenvector centrality on transitive networks for more discussion of the relationship between transitivity and sensitivity to source bias ., This suggests that measures of consensus that emphasize depth– paths through the networks –also implicitly measure consensus breadth when there is some degree of either assortativity or transitivity in the network , and work well because of these features ., In the absence of transitivity , or when transitivity is very low , depth measures like Eigenvector Centrality , should not perform well as measures of consensus , unless , as in the case of the Graph Laplacian , they explicitly incorporate Shannon information ., In the Text S1 we provide details on an additional analysis we performed to evaluate algorithm sensitivity to source bias ., The results reported in this paper and elsewhere ( 17 , see also 60–62 ) suggest that at least in social networks nodes may be making strategic decisions about social interactions using knowledge of how they are perceived by the group ., For example , the individuals in the primate study group appear to estimates of their relative power to make decisions about whether to intervene in conflicts 17 ., This requires that they have some knowledge of moments or properties of the distribution of power ( e . g . approximate variance ) ., An important question is how individuals extract this information 22 , 63 ., More generally , what do animals know about social structure and collective dynamics , how precise are their estimates , and what heuristics might they use to make calculations 64 ?, It would be useful , for example , to be able to quantify the algorithmic complexity of each algorithm so that we could rank calculations by some measure of computational difficulty ( see also 65 ) ., Ideally , we would also like to know how sensitive each algorithm is to the input data ., ( e . g . is the exact number of signals received by individual critical , or will a rough estimate do ? ) for the output distribution of power to be a useful predictor of out of sample data ., Addressing this robustness question would help to determine how much room there is to relax the mathematical requirements of a given algorithm , and find a heuristic simple enough for this study species ., Ranking the algorithms by their algorithmic complexity is a long way off , if achievable at all ., As is illustrated in Figure S1 , we can only crudely rank the algorithms given what we know about the minimum number of steps each requires in order to estimate critical quantities from an empirical perspective – the absolute power of individual , the relative power of ( e . g . where it falls in a power distribution of a given type ) , and the moments of the power distribution ., In most circumstances it seems unlikely that we , or the animals , would be interested in an isolated individuals score ., This is because it is not her power value that is important , but rather where an estimated value falls in a distribution of power scores ., Yet calculation of absolute and relative power require different computational approaches and a preliminary assessment suggests that the difficulty of these steps varies across algorithms ., We discuss these issues in greater detail in Text S1 , Section Computational complexity ., In addition to approaching the problem of complexity mathematically , we can approach it empirically by asking how sensitive the algorithms are to imperfect information in the input matrices ., For example , perhaps the individuals in our system cannot discriminate based on identity and can only remember classes of individual ( e . g . male or female , or matriline x or y , etc . ) , signals or signalers , or an interaction history of length ., By coarse-graining the input data , it is in principle possible to test how sensitive the algorithms are to this kind of imperfect information resulting from various cognitive or spatial constraints ., Aspects of this question have been addressed in previous work , as discussed in Section Sensitivity of the algorithms to source biases ., However , many questions remain open for future work ., If node function in many different systems is collectively encoded in interaction networks and this information is decodable by quantifying the agreement in network connectivity patterns , this would suggest that consensus formation is at the core of sociality ., Consider the primate society used as a model system in this paper ., Power in our primate study group is a critical social variable ., However power is not a simple variable ., The distribution of power does not map directly onto a distribution of body sizes or even a distribution of fighting abilities ., Rather it consolidates as multiple interacting individuals learn about fighting abilities and signal about this to reduce social uncertainty 14 , 19 , 21 , 22 , 63 ., When the statistics used to operationalize an aggregate social property , like power structure , are more than simple counts over strategies , and when the inputs are not simply individual traits but network data , we need to worry explicitly about the mappings between behavioral strategies and decision-making at the microscopic level and social organization 65–whether we are working with the social organization of primates or of cells forming a tissue ., A central question becomes , How do strategies get collectively combined by multiple components to produce macroscopic social properties ?, How much degeneracy characterizes this mapping ?, Once we can describe the developmental dynamics giving rise to an aggregate social property , we will be in a position to study how the social processes producing power and other kinds of social structure have evolved in a wide range of systems ., The data set , collected by J . C . Flack , is from a large , captive , breeding group of pigtailed macaques that was housed at the Yerkes National Primate Research Center in Lawrenceville , Georgia ., The physicist collaboration network was collected by Mark Newman , as described in 38 , and is available at http://www-personal . umich . edu/~mejn/netdata/ ., The data were initially collected from the Los Alamos e-Print Archive , now the arXiv at http://arxiv . org ., Since initial publication in 2001 , the network has been updated with collaborations from the arXiv through 2005 ., scientists are represented in the network and the collaborations occurred between January , 1995 and March , 2005 ., The National Science Foundation makes the data about awarded grants publicly available at http://www . nsf . gov/awards/about . jsp ., For each scientist in the collaboration network , we searched this database for any grant concerning condensed matter physics on which the scientist was one of the investigators ., If the scientist was awarded more than one grant , we summed the total amount of grants awarded him or her ., Grant data was available for of the scientists in the collaboration network ., The grants were awarded between September , 2008 and September , 2012 , with one grant starting in September , 2004 ., The functional linkage network was constructed by Lee et al . , as described in 56 and 51 , and is available at http://www . yeastnet . org/ ., Functional linkages between genes are associations that “represent functional constraints satisfied by the cell during the course of the experiments” 56 ., Evidence of a functional linkage between two genes was provided by mRNA coexpression levels , the results of protein interaction experiments , phylogenetic profiles , and the co-occurrence of the two genes in a scientific paper 51 , 56 ., Lee et al . combined these data to calculate the log-likelihood that two genes are involved in a similar function ., In our analyses , we say an edge is present if its log-likelihood score is greater than and is absent otherwise ., The resulting network has nodes ., The Saccharomyces Genome Database maintains information about the phenotypic effects of genes in the yeast genome at www . yeastgenome . org ., Two phenotypic effects reflect a genes overall importance ., One measure is the viability of organisms with a mutant version of the gene and a second measure is the competitive fitness of organisms with a mutant version of the gene ., The viability measure is binary: a mutation to a gene can lead to either a viable or an inviable organism ., An inviable organism is one that is unable to grow under standard growth conditions for S . cerevisiae , defined as glucose-containing rich medium ( YPD ) at C . A genes competitive fitn
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 nodes state or capacity to perform a function ., The algorithms capture consensus by either taking into account the number of a target nodes 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 .
Decision making in complex societies requires that individuals be aware of the groups collective opinions about themselves and their peers ., In previous work , social power , defined as the consensus about an individuals 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 individuals direct connections , correctly predict an individuals 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 .
complex systems, mathematics, ecology, applied mathematics, biology, computational biology, behavioral ecology