Month: September 2017

A physical model for efficient ranking in networks

We present a principled model and algorithm to infer a hierarchical ranking of nodes in directed networks. Unlike other methods such as minimum violation ranking, it assigns real-valued scores to nodes rather than simply ordinal ranks, and it formalizes the assumption that interactions are more likely to occur between individuals with similar ranks. It provides a natural framework for a statistical significance test for distinguishing when the inferred hierarchy is due to the network topology or is instead due to random chance, and it can be used to perform inference tasks such as predicting the existence or direction of edges. The ranking is inferred by solving a linear system of equations, which is sparse if the network is; thus the resulting algorithm is extremely efficient and scalable. We illustrate these findings by analyzing real and synthetic data and show that our method outperforms others, in both speed and accuracy, in recovering the underlying ranks and predicting edge directions. 


A physical model for efficient ranking in networks
Caterina De Bacco, Daniel B. Larremore, Cristopher Moore


Relatedness, Knowledge Diffusion, and the Evolution of Bilateral Trade

During the last decades two important contributions have reshaped our understanding of international trade. First, countries trade more with those with whom they share history, language, and culture, suggesting that trade is limited by information frictions. Second, countries are more likely to start exporting products that are similar to their current exports, suggesting that knowledge diffusion among related industries is a key constrain shaping the diversification of exports. But does knowledge about how to export to a destination also diffuses among related products and geographic neighbors? Do countries need to learn how to trade each product to each destination? Here, we use bilateral trade data from 2000 to 2015 to show that countries are more likely to increase their exports of a product to a destination when: (i) they export related products to it, (ii) they export the same product to the neighbor of a destination, (iii) they have neighbors who export the same product to that destination. Then, we explore the magnitude of these effects for new, nascent, and experienced exporters, (exporters with and without comparative advantage in a product) and also for groups of products with different level of technological sophistication. We find that the effects of product and geographic relatedness are stronger for new exporters, and also, that the effect of product relatedness is stronger for more technologically sophisticated products. These findings support the idea that international trade is shaped by information frictions that are reduced in the presence of related products and experienced geographic neighbors.


Relatedness, Knowledge Diffusion, and the Evolution of Bilateral Trade
Bogang Jun, Aamena Alshamsi, Jian Gao, Cesar A Hidalgo


Evidence of complex contagion of information in social media: An experiment using Twitter bots

It has recently become possible to study the dynamics of information diffusion in techno-social systems at scale, due to the emergence of online platforms, such as Twitter, with millions of users. One question that systematically recurs is whether information spreads according to simple or complex dynamics: does each exposure to a piece of information have an independent probability of a user adopting it (simple contagion), or does this probability depend instead on the number of sources of exposure, increasing above some threshold (complex contagion)? Most studies to date are observational and, therefore, unable to disentangle the effects of confounding factors such as social reinforcement, homophily, limited attention, or network community structure. Here we describe a novel controlled experiment that we performed on Twitter using ‘social bots’ deployed to carry out coordinated attempts at spreading information. We propose two Bayesian statistical models describing simple and complex contagion dynamics, and test the competing hypotheses. We provide experimental evidence that the complex contagion model describes the observed information diffusion behavior more accurately than simple contagion. Future applications of our results include more effective defenses against malicious propaganda campaigns on social media, improved marketing and advertisement strategies, and design of effective network intervention techniques.


Mønsted B, Sapieżyński P, Ferrara E, Lehmann S (2017) Evidence of complex contagion of information in social media: An experiment using Twitter bots. PLoS ONE 12(9): e0184148.


Three faces of entropy for complex systems: Information, thermodynamics, and the maximum entropy principle

There are at least three distinct ways to conceptualize entropy: entropy as an extensive thermodynamic quantity of physical systems (Clausius, Boltzmann, Gibbs), entropy as a measure for information production of ergodic sources (Shannon), and entropy as a means for statistical inference on multinomial processes (Jaynes maximum entropy principle). Even though these notions represent fundamentally different concepts, the functional form of the entropy for thermodynamic systems in equilibrium, for ergodic sources in information theory, and for independent sampling processes in statistical systems, is degenerate, $H(p)=\ensuremath{-}{\ensuremath{\sum}}_{i}{p}_{i}log{p}_{i}$. For many complex systems, which are typically history-dependent, nonergodic, and nonmultinomial, this is no longer the case. Here we show that for such processes, the three entropy concepts lead to different functional forms of entropy, which we will refer to as ${S}_{\mathrm{EXT}}$ for extensive entropy, ${S}_{\mathrm{IT}}$ for the source information rate in information theory, and ${S}_{\mathrm{MEP}}$ for the entropy functional that appears in the so-called maximum entropy principle, which characterizes the most likely observable distribution functions of a system. We explicitly compute these three entropy functionals for three concrete examples: for P\’olya urn processes, which are simple self-reinforcing processes, for sample-space-reducing (SSR) processes, which are simple history dependent processes that are associated with power-law statistics, and finally for multinomial mixture processes.


Peer punishment promotes enforcement of bad social norms

Social norms are an important element in explaining how humans achieve very high levels of cooperative activity. It is widely observed that, when norms can be enforced by peer punishment, groups are able to resolve social dilemmas in prosocial, cooperative ways. Here we show that punishment can also encourage participation in destructive behaviours that are harmful to group welfare, and that this phenomenon is mediated by a social norm. In a variation of a public goods game, in which the return to investment is negative for both group and individual, we find that the opportunity to punish led to higher levels of contribution, thereby harming collective payoffs. A second experiment confirmed that, independently of whether punishment is available, a majority of subjects regard the efficient behaviour of non-contribution as socially inappropriate. The results show that simply providing a punishment opportunity does not guarantee that punishment will be used for socially beneficial ends, because the social norms that influence punishment behaviour may themselves be destructive.


Peer punishment promotes enforcement of bad social norms
Klaus Abbink, Lata Gangadharan, Toby Handfield & John Thrasher
Nature Communications 8, Article number: 609 (2017)