Session K43: Complex Networks and their Applications I

Influence maximization in complex networks through optimal percolation

The whole frame of interconnections in complex networks hinges on a specific set of structural nodes, much smaller than the total size, which, if activated, would cause the spread of information to the whole network, or, if immunized, would prevent the diffusion of a large scale epidemic. Localizing this optimal, that is, minimal, set of structural nodes, called influencers, is one of the most important problems in network science. Here we map the problem onto optimal percolation in random networks to identify the minimal set of influencers, which arises by minimizing the energy of a many-body system, where the form of the interactions is fixed by the non-backtracking matrix of the network. Big data analyses reveal that the set of optimal influencers is much smaller than the one predicted by previous heuristic centralities. Remarkably, a large number of previously neglected weakly connected nodes emerges among the optimal influencers. Reference: F. Morone, H. A. Makse, Nature 524,65-68 (2015)   

Collective opinion formation on fluctuating networks

Thanks to the advent of online social networks, not only are we more connected than ever but we are also able to design and maintain our own social networks. An insight into this phenomenon will be key to understanding modern societies. To this end, we argue that active network maintenance exposes individuals to selective exposure (preference for agreeing information sources) and we explore how this could affect the structure of social networks and collective opinion formation. More technically, we investigate opinion dynamics on a complex network with fast stochastic rewiring. We show that selective exposure while inducing segregation of agents with different opinions, stabilises consensus state regardless of opinion update rules. We argue further that selective exposure can lead to a shorter time to consensus. The time to consensus has non-trivial dependence on the magnitude of selective exposure. Moreover, we find for some opinion updating rules, selective exposure can increase the lifetime of opinion segregation (polarisation of opinions).   

Choice Shift in Opinion Network Dynamics

Choice shift is a phenomenon associated with small group dynamics whereby group discussion causes group members to shift their opinions in a more extreme direction so that the mean post-discussion opinion exceeds the mean pre-discussion opinion. Also known as group polarization, choice shift is a robust experimental phenomenon and has been well-studied within social psychology. In opinion network models, shifts toward extremism are typically produced by the presence of stubborn agents at the extremes of the opinion axis, whose opinions are much more resistant to change than moderate agents. However, we present a model in which choice shift can arise without the assumption of stubborn agents; the model evolves member opinions and uncertainties using coupled nonlinear differential equations. In addition, we briefly describe the results of a recent experiment conducted involving online group discussion concerning the outcome of National Football League games are described. The model predictions concerning the effects of network structure, disagreement level, and team choice (favorite or underdog) are in accord with the experimental results.   

Social Network Influence and Personal Financial Status

Networks of social ties emerging from individual economic needs display a highly structured architecture. In response to socio-economic demands, people reshape their circle of contacts for maximizing their social status, and ipso facto, the pattern of their interconnections is strongly correlates with their personal financial situation. In this work we transform this qualitative and verbal statement into an operative definition, which allows us to quantify the economic wellness of individuals trough a measure of their collective influence. We consider the network of mobile phone calls made by the Mexican population during three months, in order to study the correlation of person's economic situation with her network location. Notably, we find that rich people tend to be also the most influential nodes, i.e., they self-organize to optimally position themselves in the network. This finding may be also raised at the level of a principle, a fact that would explain the emergence of the phenomenon of collective influence itself as the result of the local optimization of socio-economic interactions. Our method represents a powerful and efficient indicator of socio-economic robustness, which may be applied to maximize the effect of large scale economic intervention and stimulus policies   

More Opportunities than Wealth: Inequality and Emergent Social Classes in a Network of Power and Frustration

We introduce a minimal agent-based model to qualitatively conceptualize the allocation of limited wealth among more abundant opportunities. There the interplay of power, satisfaction and frustration determines the distribution, concentration, and inequality of wealth. Our framework allows us to compare subjective measures of frustration and satisfaction to collective measures of fairness in wealth distribution, such as the Lorenz curve and the Gini index. We find that a completely libertarian, law-of-the-jungle setting, where every agent can acquire wealth from, or lose wealth to, anybody else invariably leads to large inequality. The picture is however dramatically modified when hard constraints are imposed over agents, and they are limited to share wealth with neighbors on a network. We address dynamical societies via an out of equilibrium coevolution {\it of} the network, driven by a competition between power and frustration. The ratio between power and frustration controls different dynamical regimes separated by kinetic transitions and characterized by drastically different values of the indices of equality. In particular, it leads to the emergence of three self-organized social classes, lower, middle, and upper class, whose interactions drive a cyclical regime.   

Dynamic networks community detection via low rank component recovery of adjacency matrices

Dynamic community detection in networks has been of high interest due to its various applications. In this work, we apply low rank extraction technique on adjacency matrices to approximate the community structures. Not only can we accurately identify the phase transition time points where significant changes in the community structures occur, but also we can increase the accuracy of the core community structures recovered in the ‘peace’ time ranges by averaging the low rank components. A systematic methodology has been proposed as how to accomplish the target. Factor model, and stochastic block model (including weighted scenario) have been tested for the robustness of our model. Besides, applications on both Kuramoto model and US Senate Roll Call data are also carried out and interesting results are obtained.   

Multiway spectral community detection in networks

Spectral methods are widely used for community detection in networks because of their high efficiency and amenability to formal analysis. However, spectral algorithms have been limited to the division of networks into only two or three communities. Here we present a spectral algorithm that can directly divide a network into any number of communities. The algorithm makes use of a mapping from modularity maximization to a vector partitioning problem, combined with a fast heuristic for vector partitioning. We compare the performance of this spectral algorithm with previous approaches and find it to give superior results. We also give demonstrative applications of the algorithm to real-world networks and find that it produces results in good agreement with expectations for the networks studied.   

Utilizing Maximal Independent Sets as Dominating Sets in Scale-Free Networks

Dominating sets provide key solution to various critical problems in networked systems, such as detecting, monitoring, or controlling the behavior of nodes. Motivated by graph theory literature [Erdos, \textit{Israel J. Math.} \textbf{4}, 233 (1966)], we studied \textit{maximal independent sets} (MIS) as dominating sets in scale-free networks. We investigated the scaling behavior of the size of MIS in artificial scale-free networks with respect to multiple topological properties (size, average degree, power-law exponent, assortativity), evaluated its resilience to network damage resulting from random failure or targeted attack [Molnar et al., \textit{Sci. Rep.} \textbf{5}, 8321 (2015)], and compared its efficiency to previously proposed dominating set selection strategies. We showed that, despite its small set size, MIS provides very high resilience against network damage. Using extensive numerical analysis on both synthetic and real-world (social, biological, technological) network samples, we demonstrate that our method effectively satisfies four essential requirements of dominating sets for their practical applicability on large-scale real-world systems: 1.) small set size, 2.) minimal network information required for their construction scheme, 3.) fast and easy computational implementation, and 4.) resiliency to network damage.   

Growing Networks with Positive and Negative Links

Scale-free networks grown via preferential attachment have been used to model real-world networks such as the Internet, citation networks, and social networks. Here we investigate signed scale-free networks where an edge represents a positive or negative connection. We present analytic results and simulation for a growing signed network model. We compare the signed network to an unsigned scale-free network. We discuss several options for preferential attachment in a signed network that could be further adapted to model the accumulation of links over time in real-world signed networks.   

Robustness of networks of networks with degree-degree correlation

Many real-world complex systems ranging from critical infrastructure and transportation networks to living systems including brain and cellular networks are not formed by an isolated network but by a network of networks. Randomly coupled networks with interdependency between different networks may easily result in abrupt collapse. Here, we seek a possible explanation of stable functioning in natural networks of networks including functional brain networks. Specifically, we analyze the robustness of networks of networks focused on one-to-many interconnections between different networks and degree-degree correlation. Implication of the network robustness on functional brain networks of rats is also discussed.   

Degree distributions of bipartite networks and their projections

Bipartite networks play an important role in the analysis of social and economic systems as they explicitly show the conceptual links between different types of entities. As an example, it is possible to build networks to investigate interactions regarding scientific and technological innovation that are well represented by a natural bipartite structure. Since we are often most interested in only one of the node types (e.g. the authors in an author-publication network), it is common to end up working with a projected version of the underlying bipartite network. The topology of projections and the dynamics that take place on it are highly dependent on the probability distribution of nodes degrees. We use the formalism of generating functions to infer how the degree distributions of the original bipartite network affect the distribution in the projected version. Moreover, we create artificial bipartite graphs by arbitrarily choosing degree distributions for the sets of nodes and construct the projection to analyze the resulting probability distribution. Our findings show that when projecting onto a particular set of nodes, the resulting degree distribution follows the behavior of the probability distribution of such nodes, subject, however, to the tail of the opposite distribution.   

Spectra of Adjacency Matrices in Networks with Extreme Introverts and Extroverts

In recent studies of networks with preferred degrees (suitable for describing social networks in which individuals tend to prefer a certain number of contacts), the XIE model of extreme introverts and extroverts was found to display remarkable collective behavior and to raise interesting theoretical issues. Though this system is defined through its dynamics, i.e., introverts/extroverts always cut/add links, the steady state turns out to be a Boltzmann-like distribution. While the intra-group links are static, the cross-links are dynamic and lead to an ensemble of bipartite graphs, with extraordinary long-ranged correlations between elements of the incidence matrix (details in JSTAT P07013, 2015). Here, we report simulation studies of a different perspective of networks, namely, the spectra associated with this ensemble of adjacency matrices.~ As a baseline, we first consider the spectra associated with (the adjacency matrices of) a simple random (Erd\^{o}s-R\`{e}nyi) ensemble of bipartite graphs, where simulation results can be understood analytically.   

Complex root networks of Chinese characters

There are several sets of Chinese characters still available today, including Oracle Bone Inscriptions (OBI) in Shang Dynasty, Chu characters (CC) used in Chu of Warring State Period, Small Seal Script in dictionary Shuowen Jiezi (SJ) in Eastern Han Dynasty, and Kangxi Dictionary (KD) in Qing Dynasty. Such as Chinese characters were all constructed via combinations of meaningful patterns, called roots. Our studies for the complex networks of all roots indicate that the roots of the characters in OBI, CC, SJ and KD have characteristics of small world networks and scale-free networks.