Uncovering Community Structures with Initialized Bayesian Nonnegative Matrix Factorization

Uncovering community structures is important for understanding networks. Currently, several nonnegative matrix factorization algorithms have been proposed for discovering community structure in complex networks. However, these algorithms exhibit some drawbacks, such as unstable results and inefficient running times. In view of the problems, a novel approach that utilizes an initialized Bayesian nonnegative matrix factorization model for determining community membership is proposed. First, based on singular value decomposition, we obtain simple initialized matrix factorizations from approximate decompositions of the complex network’s adjacency matrix. Then, within a few iterations, the final matrix factorizations are achieved by the Bayesian nonnegative matrix factorization method with the initialized matrix factorizations. Thus, the network’s community structure can be determined by judging the classification of nodes with a final matrix factor. Experimental results show that the proposed method is highly accurate and offers competitive performance to that of the state-of-the-art methods even though it is not designed for the purpose of modularity maximization.     

Implications of Network Topology on Stability

In analogy to chemical reaction networks, I demonstrate the utility of expressing the governing equations of an arbitrary dynamical system (interaction network) as sums of real functions (generalized reactions) multiplied by real scalars (generalized stoichiometries) for analysis of its stability. The reaction stoichiometries and first derivatives define the network’s “influence topology”, a signed directed bipartite graph. Parameter reduction of the influence topology permits simplified expression of the principal minors (sums of products of non-overlapping bipartite cycles) and Hurwitz determinants (sums of products of the principal minors or the bipartite cycles directly) for assessing the network’s steady state stability. Visualization of the Hurwitz determinants over the reduced parameters defines the network’s stability phase space, delimiting the range of its dynamics (specifically, the possible numbers of unstable roots at each steady state solution). Any further explicit algebraic specification of the network will project onto this stability phase space. Stability analysis via this hierarchical approach is demonstrated on classical networks from multiple fields.     

Parrondo’s Games Based on Complex Networks and the Paradoxical Effect

Parrondo’s games were first constructed using a simple tossing scenario, which demonstrates the following paradoxical situation: in sequences of games, a winning expectation may be obtained by playing the games in a random order, although each game (game A or game B) in the sequence may result in losing when played individually. The available Parrondo’s games based on the spatial niche (the neighboring environment) are applied in the regular networks. The neighbors of each node are the same in the regular graphs, whereas they are different in the complex networks. Here, Parrondo’s model based on complex networks is proposed, and a structure of game B applied in arbitrary topologies is constructed. The results confirm that Parrondo’s paradox occurs. Moreover, the size of the region of the parameter space that elicits Parrondo’s paradox depends on the heterogeneity of the degree distributions of the networks. The higher heterogeneity yields a larger region of the parameter space where the strong paradox occurs. In addition, we use scale-free networks to show that the network size has no significant influence on the region of the parameter space where the strong or weak Parrondo’s paradox occurs. The region of the parameter space where the strong Parrondo’s paradox occurs reduces slightly when the average degree of the network increases.     

Multistability in Large Scale Models of Brain Activity

Noise driven exploration of a brain network’s dynamic repertoire has been hypothesized to be causally involved in cognitive function, aging and neurodegeneration. The dynamic repertoire crucially depends on the network’s capacity to store patterns, as well as their stability. Here we systematically explore the capacity of networks derived from human connectomes to store attractor states, as well as various network mechanisms to control the brain’s dynamic repertoire. Using a deterministic graded response Hopfield model with connectome-based interactions, we reconstruct the system’s attractor space through a uniform sampling of the initial conditions. Large fixed-point attractor sets are obtained in the low temperature condition, with a bigger number of attractors than ever reported so far. Different variants of the initial model, including (i) a uniform activation threshold or (ii) a global negative feedback, produce a similarly robust multistability in a limited parameter range. A numerical analysis of the distribution of the attractors identifies spatially-segregated components, with a centro-medial core and several well-delineated regional patches. Those different modes share similarity with the fMRI independent components observed in the “resting state” condition. We demonstrate non-stationary behavior in noise-driven generalizations of the models, with different meta-stable attractors visited along the same time course. Only the model with a global dynamic density control is found to display robust and long-lasting non-stationarity with no tendency toward either overactivity or extinction. The best fit with empirical signals is observed at the edge of multistability, a parameter region that also corresponds to the highest entropy of the attractors.     

Topology Analysis of Social Networks Extracted from Literature

In a world where complex networks are an increasingly important part of science, it is interesting to question how the new reading of social realities they provide applies to our cultural background and in particular, popular culture. Are authors of successful novels able to reproduce social networks faithful to the ones found in reality? Is there any common trend connecting an author’s oeuvre, or a genre of fiction? Such an analysis could provide new insight on how we, as a culture, perceive human interactions and consume media. The purpose of the work presented in this paper is to define the signature of a novel’s story based on the topological analysis of its social network of characters. For this purpose, an automated tool was built that analyses the dialogs in novels, identifies characters and computes their relationships in a time-dependent manner in order to assess the network’s evolution over the course of the story.     

Dynamics to Equilibrium in Network Games: Individual Behavior and Global Response

Various social contexts can be depicted as games of strategic interactions on networks, where an individual’s welfare depends on both her and her partners’ actions. Whereas much attention has been devoted to Bayes-Nash equilibria in such games, here we look at strategic interactions from an evolutionary perspective. To this end, we present the results of a numerical simulations program for these games, which allows us to find out whether Nash equilibria are accessible by adaptation of player strategies, and in general to identify the attractors of the evolution. Simulations allow us to go beyond a global characterization of the cooperativeness at equilibrium and probe into individual behavior. We find that when players imitate each other, evolution does not reach Nash equilibria and, worse, leads to very unfavorable states in terms of welfare. On the contrary, when players update their behavior rationally, they self-organize into a rich variety of Nash equilibria, where individual behavior and payoffs are shaped by the nature of the game, the social network’s structure and the players’ position within the network. Our results allow to assess the validity of mean-field approaches we use to describe the dynamics of these games. Interestingly, our dynamically-found equilibria generally do not coincide with (but show qualitatively the same features of) those resulting from theoretical predictions in the context of one-shot games under incomplete information.     

Control Centrality and Hierarchical Structure in Complex Networks

We introduce the concept of control centrality to quantify the ability of a single node to control a directed weighted network. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network’s degree distribution. We show that in a directed network without loops the control centrality of a node is uniquely determined by its layer index or topological position in the underlying hierarchical structure of the network. Inspired by the deep relation between control centrality and hierarchical structure in a general directed network, we design an efficient attack strategy against the controllability of malicious networks.     

Tinnitus-like “hallucinations” elicited by sensory deprivation in an entropy maximization recurrent neural network

Sensory deprivation has long been known to cause hallucinations or “phantom” sensations, the most common of which is tinnitus induced by hearing loss, affecting 10–20% of the population. An observable hearing loss, causing auditory sensory deprivation over a band of frequencies, is present in over 90% of people with tinnitus. Existing plasticity-based computational models for tinnitus are usually driven by homeostatic mechanisms, modeled to fit phenomenological findings. Here, we use an objective-driven learning algorithm to model an early auditory processing neuronal network, e.g., in the dorsal cochlear nucleus. The learning algorithm maximizes the network’s output entropy by learning the feed-forward and recurrent interactions in the model. We show that the connectivity patterns and responses learned by the model display several hallmarks of early auditory neuronal networks. We further demonstrate that attenuation of peripheral inputs drives the recurrent network towards its critical point and transition into a tinnitus-like state. In this state, the network activity resembles responses to genuine inputs even in the absence of external stimulation, namely, it “hallucinates” auditory responses. These findings demonstrate how objective-driven plasticity mechanisms that normally act to optimize the network’s input representation can also elicit pathologies such as tinnitus as a result of sensory deprivation.     

Complex Network Theory Applied to the Growth of Kuala Lumpur’s Public Urban Rail Transit Network

Recently, the number of studies involving complex network applications in transportation has increased steadily as scholars from various fields analyze traffic networks. Nonetheless, research on rail network growth is relatively rare. This research examines the evolution of the Public Urban Rail Transit Networks of Kuala Lumpur (PURTNoKL) based on complex network theory and covers both the topological structure of the rail system and future trends in network growth. In addition, network performance when facing different attack strategies is also assessed. Three topological network characteristics are considered: connections, clustering and centrality. In PURTNoKL, we found that the total number of nodes and edges exhibit a linear relationship and that the average degree stays within the interval [2.0488, 2.6774] with heavy-tailed distributions. The evolutionary process shows that the cumulative probability distribution (CPD) of degree and the average shortest path length show good fit with exponential distribution and normal distribution, respectively. Moreover, PURTNoKL exhibits clear cluster characteristics; most of the nodes have a 2-core value, and the CPDs of the centrality’s closeness and betweenness follow a normal distribution function and an exponential distribution, respectively. Finally, we discuss four different types of network growth styles and the line extension process, which reveal that the rail network’s growth is likely based on the nodes with the biggest lengths of the shortest path and that network protection should emphasize those nodes with the largest degrees and the highest betweenness values. This research may enhance the networkability of the rail system and better shape the future growth of public rail networks.     

Followers Are Not Enough: A Multifaceted Approach to Community Detection in Online Social Networks

In online social media networks, individuals often have hundreds or even thousands of connections, which link these users not only to friends, associates, and colleagues, but also to news outlets, celebrities, and organizations. In these complex social networks, a ‘community’ as studied in the social network literature, can have very different meaning depending on the property of the network under study. Taking into account the multifaceted nature of these networks, we claim that community detection in online social networks should also be multifaceted in order to capture all of the different and valuable viewpoints of ‘community.’ In this paper we focus on three types of communities beyond follower-based structural communities: activity-based, topic-based, and interaction-based. We analyze a Twitter dataset using three different weightings of the structural network meant to highlight these three community types, and then infer the communities associated with these weightings. We show that interesting insights can be obtained about the complex community structure present in social networks by studying when and how these four community types give rise to similar as well as completely distinct community structure.     

Emergence of Super Cooperation of Prisoner’s Dilemma Games on Scale-Free Networks

Recently, the authors proposed a quantum prisoner’s dilemma game based on the spatial game of Nowak and May, and showed that the game can be played classically. By using this idea, we proposed three generalized prisoner’s dilemma (GPD, for short) games based on the weak Prisoner’s dilemma game, the full prisoner’s dilemma game and the normalized Prisoner’s dilemma game, written by GPD_W, GPD_F and GPD_N respectively. Our games consist of two players, each of which has three strategies: cooperator (C), defector (D) and super cooperator (denoted by Q), and have a parameter γ to measure the entangled relationship between the two players. We found that our generalised prisoner’s dilemma games have new Nash equilibrium principles, that entanglement is the principle of emergence and convergence (i.e., guaranteed emergence) of super cooperation in evolutions of our generalised prisoner’s dilemma games on scale-free networks, that entanglement provides a threshold for a phase transition of super cooperation in evolutions of our generalised prisoner’s dilemma games on scale-free networks, that the role of heterogeneity of the scale-free networks in cooperations and super cooperations is very limited, and that well-defined structures of scale-free networks allow coexistence of cooperators and super cooperators in the evolutions of the weak version of our generalised prisoner’s dilemma games.     

Community Size Effects on Epidemic Spreading in Multiplex Social Networks

The dynamical process of epidemic spreading has drawn much attention of the complex network community. In the network paradigm, diseases spread from one person to another through the social ties amongst the population. There are a variety of factors that govern the processes of disease spreading on the networks. A common but not negligible factor is people’s reaction to the outbreak of epidemics. Such reaction can be related information dissemination or self-protection. In this work, we explore the interactions between disease spreading and population response in terms of information diffusion and individuals’ alertness. We model the system by mapping multiplex networks into two-layer networks and incorporating individuals’ risk awareness, on the assumption that their response to the disease spreading depends on the size of the community they belong to. By comparing the final incidence of diseases in multiplex networks, we find that there is considerable mitigation of diseases spreading for full phase of spreading speed when individuals’ protection responses are introduced. Interestingly, the degree of community overlap between the two layers is found to be critical factor that affects the final incidence. We also analyze the consequences of the epidemic incidence in communities with different sizes and the impacts of community overlap between two layers. Specifically, as the diseases information makes individuals alert and take measures to prevent the diseases, the effective protection is more striking in small community. These phenomena can be explained by the multiplexity of the networked system and the competition between two spreading processes.     

Social structure of primate interaction networks facilitates the emergence of cooperation

Animal cooperation has puzzled biologists for a long time as its existence seems to contravene the basic notion of evolutionary biology that natural selection favours ‘selfish’ genes that promote only their own well-being. Evolutionary game theory has shown that cooperators can prosper in populations of selfish individuals if they occur in clusters, interacting more frequently with each other than with the selfish. Here we show that social networks of primates possess the necessary social structure to promote the emergence of cooperation. By simulating evolutionary dynamics of cooperative behaviour on interaction networks of 70 primate groups, we found that for most groups network reciprocity augmented the fixation probability for cooperation. The variation in the strength of this effect can be partly explained by the groups’ community modularity—a network measure for the groups’ heterogeneity. Thus, given selective update and partner choice mechanisms, network reciprocity has the potential to explain socially learned forms of cooperation in primate societies.     

A Graph Theoretical Approach to Study the Organization of the Cortical Networks during Different Mathematical Tasks

The two core systems of mathematical processing (subitizing and retrieval) as well as their functionality are already known and published. In this study we have used graph theory to compare the brain network organization of these two core systems in the cortical layer during difficult calculations. We have examined separately all the EEG frequency bands in healthy young individuals and we found that the network organization at rest, as well as during mathematical tasks has the characteristics of Small World Networks for all the bands, which is the optimum organization required for efficient information processing. The different mathematical stimuli provoked changes in the graph parameters of different frequency bands, especially the low frequency bands. More specific, in Delta band the induced network increases it’s local and global efficiency during the transition from subitizing to retrieval system, while results suggest that difficult mathematics provoke networks with higher cliquish organization due to more specific demands. The network of the Theta band follows the same pattern as before, having high nodal and remote organization during difficult mathematics. Also the spatial distribution of the network’s weights revealed more prominent connections in frontoparietal regions, revealing the working memory load due to the engagement of the retrieval system. The cortical networks of the alpha brainwaves were also more efficient, both locally and globally, during difficult mathematics, while the fact that alpha’s network was more dense on the frontparietal regions as well, reveals the engagement of the retrieval system again. Concluding, this study gives more evidences regarding the interaction of the two core systems, exploiting the produced functional networks of the cerebral cortex, especially for the difficult mathematics.     

Place-Based Attributes Predict Community Membership in a Mobile Phone Communication Network

Social networks can be organized into communities of closely connected nodes, a property known as modularity. Because diseases, information, and behaviors spread faster within communities than between communities, understanding modularity has broad implications for public policy, epidemiology and the social sciences. Explanations for community formation in social networks often incorporate the attributes of individual people, such as gender, ethnicity or shared activities. High modularity is also a property of large-scale social networks, where each node represents a population of individuals at a location, such as call flow between mobile phone towers. However, whether or not place-based attributes, including land cover and economic activity, can predict community membership for network nodes in large-scale networks remains unknown. We describe the pattern of modularity in a mobile phone communication network in the Dominican Republic, and use a linear discriminant analysis (LDA) to determine whether geographic context can explain community membership. Our results demonstrate that place-based attributes, including sugar cane production, urbanization, distance to the nearest airport, and wealth, correctly predicted community membership for over 70% of mobile phone towers. We observed a strongly positive correlation (r = 0.97) between the modularity score and the predictive ability of the LDA, suggesting that place-based attributes can accurately represent the processes driving modularity. In the absence of social network data, the methods we present can be used to predict community membership over large scales using solely place-based attributes.     

Detection of the Elite Structure in a Virtual Multiplex Social System by Means of a Generalised K-Core

Elites are subgroups of individuals within a society that have the ability and means to influence, lead, govern, and shape societies. Members of elites are often well connected individuals, which enables them to impose their influence to many and to quickly gather, process, and spread information. Here we argue that elites are not only composed of highly connected individuals, but also of intermediaries connecting hubs to form a cohesive and structured elite-subgroup at the core of a social network. For this purpose we present a generalization of the -core algorithm that allows to identify a social core that is composed of well-connected hubs together with their ‘connectors’. We show the validity of the idea in the framework of a virtual world defined by a massive multiplayer online game, on which we have complete information of various social networks. Exploiting this multiplex structure, we find that the hubs of the generalised -core identify those individuals that are high social performers in terms of a series of indicators that are available in the game. In addition, using a combined strategy which involves the generalised -core and the recently introduced -core, the elites of the different ’nations’ present in the game are perfectly identified as modules of the generalised -core. Interesting sudden shifts in the composition of the elite cores are observed at deep levels. We show that elite detection with the traditional -core is not possible in a reliable way. The proposed method might be useful in a series of more general applications, such as community detection.     

The Effect of Ostracism and Optional Participation on the Evolution of Cooperation in the Voluntary Public Goods Game

Not only animals, plants and microbes but also humans cooperate in groups. The evolution of cooperation in a group is an evolutionary puzzle, because defectors always obtain a higher benefit than cooperators. When people participate in a group, they evaluate group member’s reputations and then decide whether to participate in it. In some groups, membership is open to all who are willing to participate in the group. In other groups, a candidate is excluded from membership if group members regard the candidate’s reputation as bad. We developed an evolutionary game model and investigated how participation in groups and ostracism influence the evolution of cooperation in groups when group members play the voluntary public goods game, by means of computer simulation. When group membership is open to all candidates and those candidates can decide whether to participate in a group, cooperation cannot be sustainable. However, cooperation is sustainable when a candidate cannot be a member unless all group members admit them to membership. Therefore, it is not participation in a group but rather ostracism, which functions as costless punishment on defectors, that is essential to sustain cooperation in the voluntary public goods game.     

Form-Finding Model Shows How Cytoskeleton Network Stiffness Is Realized

In eukaryotic cells the actin-cytoskeletal network provides stiffness and the driving force that contributes to changes in cell shape and cell motility, but the elastic behavior of this network is not well understood. In this paper a two dimensional form-finding model is proposed to investigate the elasticity of the actin filament network. Utilizing an initially random array of actin filaments and actin-cross-linking proteins the form-finding model iterates until the random array is brought into a stable equilibrium configuration. With some care given to actin filament density and length, distance between host sites for cross-linkers, and overall domain size the resulting configurations from the form-finding model are found to be topologically similar to cytoskeletal networks in real cells. The resulting network may then be mechanically exercised to explore how the actin filaments deform and align under load and the sensitivity of the network’s stiffness to actin filament density, length, etc. Results of the model are consistent with the experimental literature, e.g. actin filaments tend to re-orient in the direction of stretching; and the filament relative density, filament length, and actin-cross-linking protein’s relative density, control the actin-network stiffness. The model provides a ready means of extension to more complicated domains and a three-dimensional form-finding model is under development as well as models studying the formation of actin bundles.     

Where’s the Noise? Key Features of Spontaneous Activity and Neural Variability Arise through Learning in a Deterministic Network

Even in the absence of sensory stimulation the brain is spontaneously active. This background “noise” seems to be the dominant cause of the notoriously high trial-to-trial variability of neural recordings. Recent experimental observations have extended our knowledge of trial-to-trial variability and spontaneous activity in several directions: 1. Trial-to-trial variability systematically decreases following the onset of a sensory stimulus or the start of a motor act. 2. Spontaneous activity states in sensory cortex outline the region of evoked sensory responses. 3. Across development, spontaneous activity aligns itself with typical evoked activity patterns. 4. The spontaneous brain activity prior to the presentation of an ambiguous stimulus predicts how the stimulus will be interpreted. At present it is unclear how these observations relate to each other and how they arise in cortical circuits. Here we demonstrate that all of these phenomena can be accounted for by a deterministic self-organizing recurrent neural network model (SORN), which learns a predictive model of its sensory environment. The SORN comprises recurrently coupled populations of excitatory and inhibitory threshold units and learns via a combination of spike-timing dependent plasticity (STDP) and homeostatic plasticity mechanisms. Similar to balanced network architectures, units in the network show irregular activity and variable responses to inputs. Additionally, however, the SORN exhibits sequence learning abilities matching recent findings from visual cortex and the network’s spontaneous activity reproduces the experimental findings mentioned above. Intriguingly, the network’s behaviour is reminiscent of sampling-based probabilistic inference, suggesting that correlates of sampling-based inference can develop from the interaction of STDP and homeostasis in deterministic networks. We conclude that key observations on spontaneous brain activity and the variability of neural responses can be accounted for by a simple deterministic recurrent neural network which learns a predictive model of its sensory environment via a combination of generic neural plasticity mechanisms.