A Novel Top-k Strategy for Influence Maximization in Complex Networks with Community Structure

In complex networks, it is of great theoretical and practical significance to identify a set of critical spreaders which help to control the spreading process. Some classic methods are proposed to identify multiple spreaders. However, they sometimes have limitations for the networks with community structure because many chosen spreaders may be clustered in a community. In this paper, we suggest a novel method to identify multiple spreaders from communities in a balanced way. The network is first divided into a great many super nodes and then k spreaders are selected from these super nodes. Experimental results on real and synthetic networks with community structure show that our method outperforms the classic methods for degree centrality, k-core and ClusterRank in most cases.     

Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about nodes, more than 15 times faster than PageRank.     

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.     

Estimation of Global Network Statistics from Incomplete Data

Complex networks underlie an enormous variety of social, biological, physical, and virtual systems. A profound complication for the science of complex networks is that in most cases, observing all nodes and all network interactions is impossible. Previous work addressing the impacts of partial network data is surprisingly limited, focuses primarily on missing nodes, and suggests that network statistics derived from subsampled data are not suitable estimators for the same network statistics describing the overall network topology. We generate scaling methods to predict true network statistics, including the degree distribution, from only partial knowledge of nodes, links, or weights. Our methods are transparent and do not assume a known generating process for the network, thus enabling prediction of network statistics for a wide variety of applications. We validate analytical results on four simulated network classes and empirical data sets of various sizes. We perform subsampling experiments by varying proportions of sampled data and demonstrate that our scaling methods can provide very good estimates of true network statistics while acknowledging limits. Lastly, we apply our techniques to a set of rich and evolving large-scale social networks, Twitter reply networks. Based on 100 million tweets, we use our scaling techniques to propose a statistical characterization of the Twitter Interactome from September 2008 to November 2008. Our treatment allows us to find support for Dunbar''s hypothesis in detecting an upper threshold for the number of active social contacts that individuals maintain over the course of one week.     

The Critical Periphery in the Growth of Social Protests

Social media have provided instrumental means of communication in many recent political protests. The efficiency of online networks in disseminating timely information has been praised by many commentators; at the same time, users are often derided as “slacktivists” because of the shallow commitment involved in clicking a forwarding button. Here we consider the role of these peripheral online participants, the immense majority of users who surround the small epicenter of protests, representing layers of diminishing online activity around the committed minority. We analyze three datasets tracking protest communication in different languages and political contexts through the social media platform Twitter and employ a network decomposition technique to examine their hierarchical structure. We provide consistent evidence that peripheral participants are critical in increasing the reach of protest messages and generating online content at levels that are comparable to core participants. Although committed minorities may constitute the heart of protest movements, our results suggest that their success in maximizing the number of online citizens exposed to protest messages depends, at least in part, on activating the critical periphery. Peripheral users are less active on a per capita basis, but their power lies in their numbers: their aggregate contribution to the spread of protest messages is comparable in magnitude to that of core participants. An analysis of two other datasets unrelated to mass protests strengthens our interpretation that core-periphery dynamics are characteristically important in the context of collective action events. Theoretical models of diffusion in social networks would benefit from increased attention to the role of peripheral nodes in the propagation of information and behavior.     

Geographies of an Online Social Network

How is online social media activity structured in the geographical space? Recent studies have shown that in spite of earlier visions about the “death of distance”, physical proximity is still a major factor in social tie formation and maintenance in virtual social networks. Yet, it is unclear, what are the characteristics of the distance dependence in online social networks. In order to explore this issue the complete network of the former major Hungarian online social network is analyzed. We find that the distance dependence is weaker for the online social network ties than what was found earlier for phone communication networks. For a further analysis we introduced a coarser granularity: We identified the settlements with the nodes of a network and assigned two kinds of weights to the links between them. When the weights are proportional to the number of contacts we observed weakly formed, but spatially based modules resemble to the borders of macro-regions, the highest level of regional administration in the country. If the weights are defined relative to an uncorrelated null model, the next level of administrative regions, counties are reflected.     

Dimensionality of Social Networks Using Motifs and Eigenvalues

We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an m-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when m scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.     

Rich-Cores in Networks

A core comprises of a group of central and densely connected nodes which governs the overall behaviour of a network. It is recognised as one of the key meso-scale structures in complex networks. Profiling this meso-scale structure currently relies on a limited number of methods which are often complex and parameter dependent or require a null model. As a result, scalability issues are likely to arise when dealing with very large networks together with the need for subjective adjustment of parameters. The notion of a rich-club describes nodes which are essentially the hub of a network, as they play a dominating role in structural and functional properties. The definition of a rich-club naturally emphasises high degree nodes and divides a network into two subgroups. Here, we develop a method to characterise a rich-core in networks by theoretically coupling the underlying principle of a rich-club with the escape time of a random walker. The method is fast, scalable to large networks and completely parameter free. In particular, we show that the evolution of the core in World Trade and C. elegans networks correspond to responses to historical events and key stages in their physical development, respectively.     

Information Filtering on Coupled Social Networks

In this paper, based on the coupled social networks (CSN), we propose a hybrid algorithm to nonlinearly integrate both social and behavior information of online users. Filtering algorithm, based on the coupled social networks, considers the effects of both social similarity and personalized preference. Experimental results based on two real datasets, Epinions and Friendfeed, show that the hybrid pattern can not only provide more accurate recommendations, but also enlarge the recommendation coverage while adopting global metric. Further empirical analyses demonstrate that the mutual reinforcement and rich-club phenomenon can also be found in coupled social networks where the identical individuals occupy the core position of the online system. This work may shed some light on the in-depth understanding of the structure and function of coupled social networks.     

Nodes Having a Major Influence to Break Cooperation Define a Novel Centrality Measure: Game Centrality

Cooperation played a significant role in the self-organization and evolution of living organisms. Both network topology and the initial position of cooperators heavily affect the cooperation of social dilemma games. We developed a novel simulation program package, called ‘NetworGame’, which is able to simulate any type of social dilemma games on any model, or real world networks with any assignment of initial cooperation or defection strategies to network nodes. The ability of initially defecting single nodes to break overall cooperation was called as ‘game centrality’. The efficiency of this measure was verified on well-known social networks, and was extended to ‘protein games’, i.e. the simulation of cooperation between proteins, or their amino acids. Hubs and in particular, party hubs of yeast protein-protein interaction networks had a large influence to convert the cooperation of other nodes to defection. Simulations on methionyl-tRNA synthetase protein structure network indicated an increased influence of nodes belonging to intra-protein signaling pathways on breaking cooperation. The efficiency of single, initially defecting nodes to convert the cooperation of other nodes to defection in social dilemma games may be an important measure to predict the importance of nodes in the integration and regulation of complex systems. Game centrality may help to design more efficient interventions to cellular networks (in forms of drugs), to ecosystems and social networks.     

The Rücker–Markov invariants of complex Bio-Systems: Applications in Parasitology and Neuroinformatics

Rücker's walk count (WC) indices are well-known topological indices (TIs) used in Chemoinformatics to quantify the molecular structure of drugs represented by a graph in Quantitative structure–activity/property relationship (QSAR/QSPR) studies. In this work, we introduce for the first time the higher-order (kth order) analogues (WC_k) of these indices using Markov chains. In addition, we report new QSPR models for large complex networks of different Bio-Systems useful in Parasitology and Neuroinformatics. The new type of QSPR models can be used for model checking to calculate numerical scores S(L_ij) for links L_ij (checking or re-evaluation of network connectivity) in large networks of all these fields. The method may be summarized as follows: (i) first, the WC_k(j) values are calculated for all jth nodes in a complex network already created; (ii) A linear discriminant analysis (LDA) is used to seek a linear equation that discriminates connected or linked (L_ij = 1) pairs of nodes experimentally confirmed from non-linked ones (L_ij = 0); (iii) The new model is validated with external series of pairs of nodes; (iv) The equation obtained is used to re-evaluate the connectivity quality of the network, connecting/disconnecting nodes based on the quality scores calculated with the new connectivity function. The linear QSPR models obtained yielded the following results in terms of overall test accuracy for re-construction of complex networks of different Bio-Systems: parasite–host networks (93.14%), NW Spain fasciolosis spreading networks (71.42/70.18%) and CoCoMac Brain Cortex co-activation network (86.40%). Thus, this work can contribute to the computational re-evaluation or model checking of connectivity (collation) in complex systems of any science field.     

Ambiguity in Social Network Data for Presence,Sensitive-Attribute,Degree and Relationship Privacy Protection

Maintaining privacy in network data publishing is a major challenge. This is because known characteristics of individuals can be used to extract new information about them. Recently, researchers have developed privacy methods based on k-anonymity and l-diversity to prevent re-identification or sensitive label disclosure through certain structural information. However, most of these studies have considered only structural information and have been developed for undirected networks. Furthermore, most existing approaches rely on generalization and node clustering so may entail significant information loss as all properties of all members of each group are generalized to the same value. In this paper, we introduce a framework for protecting sensitive attribute, degree (the number of connected entities), and relationships, as well as the presence of individuals in directed social network data whose nodes contain attributes. First, we define a privacy model that specifies privacy requirements for the above private information. Then, we introduce the technique of Ambiguity in Social Network data (ASN) based on anatomy, which specifies how to publish social network data. To employ ASN, individuals are partitioned into groups. Then, ASN publishes exact values of properties of individuals of each group with common group ID in several tables. The lossy join of those tables based on group ID injects uncertainty to reconstruct the original network. We also show how to measure different privacy requirements in ASN. Simulation results on real and synthetic datasets demonstrate that our framework, which protects from four types of private information disclosure, preserves data utility in tabular, topological and spectrum aspects of networks at a satisfactory level.     

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.     

Social features of online networks: the strength of intermediary ties in online social media

An increasing fraction of today's social interactions occur using online social media as communication channels. Recent worldwide events, such as social movements in Spain or revolts in the Middle East, highlight their capacity to boost people's coordination. Online networks display in general a rich internal structure where users can choose among different types and intensity of interactions. Despite this, there are still open questions regarding the social value of online interactions. For example, the existence of users with millions of online friends sheds doubts on the relevance of these relations. In this work, we focus on Twitter, one of the most popular online social networks, and find that the network formed by the basic type of connections is organized in groups. The activity of the users conforms to the landscape determined by such groups. Furthermore, Twitter's distinction between different types of interactions allows us to establish a parallelism between online and offline social networks: personal interactions are more likely to occur on internal links to the groups (the weakness of strong ties); events transmitting new information go preferentially through links connecting different groups (the strength of weak ties) or even more through links connecting to users belonging to several groups that act as brokers (the strength of intermediary ties).     

Social network structure and parasite infection patterns in a territorial reptile, the tuatara (Sphenodon punctatus)

We investigated whether the parasite load of an individual could be predicted by its position in a social network. Specifically, we derived social networks in a solitary, territorial reptile (the tuatara, Sphenodon punctatus), with links based on the sharing of space, not necessarily synchronously, in overlapping territories. Tuatara are infected by ectoparasitic ticks (Amblyomma sphenodonti), mites (Neotrombicula spp.) and a blood parasite (Hepatozoon tuatarae) which is transmitted by the tick. We recorded the location of individual tuatara in two study plots twice daily during the mating season (March) in 2 years (2006 and 2007) on Stephens Island, New Zealand. We constructed weighted, directed networks to represent pathways for parasite transmission, where nodes represented individual tuatara and edges connecting the nodes represented the extent of territory overlap among each pair of individuals. We considered a network-based hypothesis which predicted that the in-strength of individuals (the sum of edge weights directed towards a node) in the derived network would be positively related to their parasite load. Alternatively, if the derived social network did not reflect actual parasite transmission, we predicted other factors such as host sex, size or territory size may better explain variation in parasite infection patterns. We found clear positive relationships between the in-strength of tuatara and their tick loads, and infection patterns with tick-borne blood parasites. In particular, the extent that individuals were connected to males in the network consistently predicted tick loads of tuatara. However, mite loads of tuatara were significantly related to host sex, body size and territory size, and showed little association with network measures. The results suggest that the pathway of transmission of parasites through a population will depend on the transmission mechanism of the parasite, but that social networks provide a powerful predictive tool for some parasites.     

Similar Pathogen Targets in Arabidopsis thaliana and Homo sapiens Protein Networks

We study the behavior of pathogens on host protein networks for humans and Arabidopsis - noting striking similarities. Specifically, we preform -shell decomposition analysis on these networks - which groups the proteins into various “shells” based on network structure. We observe that shells with a higher average degree are more highly targeted (with a power-law relationship) and that highly targeted nodes lie in shells closer to the inner-core of the network. Additionally, we also note that the inner core of the network is significantly under-targeted. We show that these core proteins may have a role in intra-cellular communication and hypothesize that they are less attacked to ensure survival of the host. This may explain why certain high-degree proteins are not significantly attacked.     

Topological characteristics of target genes regulated by abiotic-stress-responsible miRNAs in a rice interactome network

A great number of microRNAs (miRNAs) have been identified in responding and acting in gene regulatory networks associated with plant tolerance to abiotic stress conditions, such as drought, salinity, and high temperature. The topological exploration of target genes regulated by abiotic-stress-responsible miRNAs (ASRmiRs) in a network facilitates to discover the molecular basis of plant abiotic stress response. This study was based on the staple food rice (Oryza sativa) in which ASRmiRs were manually curated. After having compared the topological properties of target genes (stress-miR-targets) with those (non-stress-miR-targets) not regulated by ASRmiRs in a rice interactome network, we found that stress-miR-targets exhibited distinguishable topological properties. The interaction probability analysis and k-core decomposition showed that stress-miR-targets preferentially interacted with non-stress-miR-targets and located at the peripheral positions in the network. Our results indicated an obvious topological distinction between the two types of genes, reflecting the specific mechanisms of action of stress-miR-targets in rice abiotic stress response. Also, the results may provide valuable clues to elucidate molecular mechanisms of crop response to abiotic stress.     

Qualities and Inequalities in Online Social Networks through the Lens of the Generalized Friendship Paradox

The friendship paradox is the phenomenon that in social networks, people on average have fewer friends than their friends do. The generalized friendship paradox is an extension to attributes other than the number of friends. The friendship paradox and its generalized version have gathered recent attention due to the information they provide about network structure and local inequalities. In this paper, we propose several measures of nodal qualities which capture different aspects of their activities and influence in online social networks. Using these measures we analyse the prevalence of the generalized friendship paradox over Twitter and we report high levels of prevalence (up to over 90% of nodes). We contend that this prevalence of the friendship paradox and its generalized version arise because of the hierarchical nature of the connections in the network. This hierarchy is nested as opposed to being star-like. We conclude that these paradoxes are collective phenomena not created merely by a minority of well-connected or high-attribute nodes. Moreover, our results show that a large fraction of individuals can experience the generalized friendship paradox even in the absence of a significant correlation between degrees and attributes.