Models of social networks based on social distance attachment

Identifying influential nodes based on the disassortativity and community structure of complex network

The complex networks exhibit significant heterogeneity in node connections, resulting in a few nodes playing critical roles in various scenarios, including decision-making, disease control, and population immunity. Therefore, accurately identifying these influential nodes that play crucial roles in networks is very important. Many methods have been proposed in different fields to solve this issue. This paper focuses on the different types of disassortativity existing in networks and innovatively introduces the concept of disassortativity of the node, namely, the inconsistency between the degree of a node and the degrees of its neighboring nodes, and proposes a measure of disassortativity of the node (DoN) by a step function. Furthermore, the paper analyzes and indicates that in many real-world network applications, such as online social networks, the influence of nodes within the network is often associated with disassortativity of the node and the community boundary structure of the network. Thus, the influential metric of node based on disassortativity and community structure (mDC) is proposed. Extensive experiments are conducted in synthetic and real networks, and the performance of the DoN and mDC is validated through network robustness experiments and immune experiment of disease infection. Experimental and analytical results demonstrate that compared to other state-of-the-art centrality measures, the proposed methods (DoN and mDC) exhibits superior identification performance and efficiency, particularly in non-disassortative networks and networks with clear community structures. Furthermore, we find that the DoN and mDC exhibit high stability to network noise and inaccuracies of the network data.

Cavity approach for the approximation of spectral density of graphs with heterogeneous structures

Graphs have become widely used to represent and study social, biological, and technological systems. Statistical methods to analyze empirical graphs were proposed based on the graph's spectral density. However, their running time is cubic in the number of vertices, precluding direct application to large instances. Thus, efficient algorithms to calculate the spectral density become necessary. For sparse graphs, the cavity method can efficiently approximate the spectral density of locally treelike undirected and directed graphs. However, it does not apply to most empirical graphs because they have heterogeneous structures. Thus, we propose methods for undirected and directed graphs with heterogeneous structures using a new vertex's neighborhood definition and the cavity approach. Our methods' time and space complexities are O(|E|h_{max}^{3}t) and O(|E|h_{max}^{2}t), respectively, where |E| is the number of edges, h_{max} is the size of the largest local neighborhood of a vertex, and t is the number of iterations required for convergence. We demonstrate the practical efficacy by estimating the spectral density of simulated and real-world undirected and directed graphs.

Percolation and Topological Properties of Temporal Higher-Order Networks

Many complex systems that exhibit temporal nonpairwise interactions can be represented by means of generative higher-order network models. Here, we propose a hidden variable formalism to analytically characterize a general class of higher-order network models. We apply our framework to a temporal higher-order activity-driven model, providing analytical expressions for the main topological properties of the time-integrated hypergraphs, depending on the integration time and the activity distributions characterizing the model. Furthermore, we provide analytical estimates for the percolation times of general classes of uncorrelated and correlated hypergraphs. Finally, we quantify the extent to which the percolation time of empirical social interactions is underestimated when their higher-order nature is neglected.

Evolutionary characteristics of global offshore carbon emissions network and responsibility allocation of emissions reduction

Offshore carbon emissions from the international shipping trade are significant contributors to climate change. Based on the complex shipping trade networks, offshore carbon emissions are correlated rather than independent, and allocating responsibility for reducing emissions does not depend solely on the amount but on linkages. We use the global container shipping data covering more than 98% of routes from 2015 to 2020 to calculate the offshore carbon emissions from shipping. Subsequently, we construct an offshore carbon emissions network based on the shipping routes and emissions to identify the evolutionary tendency of network and clarify emissions reduction responsibilities by considering equity and efficiency. We discover that global offshore carbon emissions present a complicated network structure dominated by developed countries and large economies. Countries on the same continent or within the same economic organizations have closer and more frequent carbon correlations. Greater responsibilities should be allocated to countries who are at the center of the network.

Heterogeneous message passing for heterogeneous networks

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

Density-Based Entropy Centrality for Community Detection in Complex Networks

One of the most important problems in complex networks is the location of nodes that are essential or play a main role in the network. Nodes with main local roles are the centers of real communities. Communities are sets of nodes of complex networks and are densely connected internally. Choosing the right nodes as seeds of the communities is crucial in determining real communities. We propose a new centrality measure named density-based entropy centrality for the local identification of the most important nodes. It measures the entropy of the sum of the sizes of the maximal cliques to which each node and its neighbor nodes belong. The proposed centrality is a local measure for explaining the local influence of each node, which provides an efficient way to locally identify the most important nodes and for community detection because communities are local structures. It can be computed independently for individual vertices, for large networks, and for not well-specified networks. The use of the proposed density-based entropy centrality for community seed selection and community detection outperforms other centrality measures.

Identifying Influential Nodes in Social Networks: Exploiting Self-Voting Mechanism

The influence maximization (IM) problem is defined as identifying a group of influential nodes in a network such that these nodes can affect as many nodes as possible. Due to its great significance in viral marketing, disease control, social recommendation, and so on, considerable efforts have been devoted to the development of methods to solve the IM problem. In the literature, VoteRank and its improved algorithms have been proposed to select influential nodes based on voting approaches. However, in the voting process of these algorithms, a node cannot vote for itself. We argue that this voting schema runs counter to many real scenarios. To address this issue, we designed the VoteRank* algorithm, in which we first introduce the self-voting mechanism into the voting process. In addition, we also take into consideration the diversities of nodes. More explicitly, we measure the voting ability of nodes and the amount of a node voting for its neighbors based on the H-index of nodes. The effectiveness of the proposed algorithm is experimentally verified on 12 benchmark networks. The results demonstrate that VoteRank* is superior to the baseline methods in most cases.

A Two-Phase Feature Selection Method for Identifying Influential Spreaders of Disease Epidemics in Complex Networks

Network epidemiology plays a fundamental role in understanding the relationship between network structure and epidemic dynamics, among which identifying influential spreaders is especially important. Most previous studies aim to propose a centrality measure based on network topology to reflect the influence of spreaders, which manifest limited universality. Machine learning enhances the identification of influential spreaders by combining multiple centralities. However, several centrality measures utilized in machine learning methods, such as closeness centrality, exhibit high computational complexity when confronted with large network sizes. Here, we propose a two-phase feature selection method for identifying influential spreaders with a reduced feature dimension. Depending on the definition of influential spreaders, we obtain the optimal feature combination for different synthetic networks. Our results demonstrate that when the datasets are mildly or moderately imbalanced, for Barabasi-Albert (BA) scale-free networks, the centralities' combination with the two-hop neighborhood is fundamental, and for Erdős-Rényi (ER) random graphs, the centralities' combination with the degree centrality is essential. Meanwhile, for Watts-Strogatz (WS) small world networks, feature selection is unnecessary. We also conduct experiments on real-world networks, and the features selected display a high similarity with synthetic networks. Our method provides a new path for identifying superspreaders for the control of epidemics.

Belief propagation on networks with cliques and chordless cycles

It is well known that tree-based theories can describe the properties of undirected clustered networks with extremely accurate results [S. Melnik et al., Phys. Rev. E 83, 036112 (2011)10.1103/PhysRevE.83.036112]. It is reasonable to suggest that a motif-based theory would be superior to a tree one, since additional neighbor correlations are encapsulated in the motif structure. In this paper, we examine bond percolation on random and real world networks using belief propagation in conjunction with edge-disjoint motif covers. We derive exact message passing expressions for cliques and chordless cycles of finite size. Our theoretical model gives good agreement with Monte Carlo simulation and offers a simple, yet substantial improvement on traditional message passing, showing that this approach is suitable to study the properties of random and empirical networks.

Influence maximization: Divide and conquer

The problem of influence maximization, i.e., finding the set of nodes having maximal influence on a network, is of great importance for several applications. In the past two decades, many heuristic metrics to spot influencers have been proposed. Here, we introduce a framework to boost the performance of such metrics. The framework consists in dividing the network into sectors of influence, and then selecting the most influential nodes within these sectors. We explore three different methodologies to find sectors in a network: graph partitioning, graph hyperbolic embedding, and community structure. The framework is validated with a systematic analysis of real and synthetic networks. We show that the gain in performance generated by dividing a network into sectors before selecting the influential spreaders increases as the modularity and heterogeneity of the network increase. Also, we show that the division of the network into sectors can be efficiently performed in a time that scales linearly with the network size, thus making the framework applicable to large-scale influence maximization problems.

Identifying important nodes in complex networks based on extended degree and E-shell hierarchy decomposition

The identification of important nodes is a hot topic in complex networks. Many methods have been proposed in different fields for solving this problem. Most previous work emphasized the role of a single feature and, as a result, rarely made full use of multiple items. This paper proposes a new method that utilizes multiple characteristics of nodes for the evaluation of their importance. First, an extended degree is defined to improve the classical degree. And E-shell hierarchy decomposition is put forward for determining nodes' position through the network's hierarchical structure. Then, based on the combination of these two components, a hybrid characteristic centrality and its extended version are proposed for evaluating the importance of nodes. Extensive experiments are conducted in six real networks, and the susceptible-infected-recovered model and monotonicity criterion are introduced to test the performance of the new approach. The comparison results demonstrate that the proposed new approach exposes more competitive advantages in both accuracy and resolution compared to the other five approaches.

Density and node closeness based clustering method for community detection

In a real-world, networked system, the ability to detect communities or clusters has piqued the concern of researchers in a wide range of fields. Many existing methods are simply meant to detect the membership of communities, not the structures of those groups, which is a limitation. We contend that community structures at the local level can also provide valuable insight into their detection. In this study, we developed a simple yet prosperous way of uncovering communities and their cores at the same time while keeping things simple. Essentially, the concept is founded on the theory that the structure of a community may be thought of as a high-density node surrounded by neighbors of minor densities and that community centers are located at a significant distance from one another. We propose a concept termed “community centrality” based on finding motifs to measure the probability of a node becoming the community center in a setting like this and then disseminate multiple, substantial center probabilities all over the network through a node closeness score mechanism. The experimental results show that the proposed method is more efficient than many other already used methods.

Sharpest possible clustering bounds using robust random graph analysis

Complex network theory crucially depends on the assumptions made about the degree distribution, while fitting degree distributions to network data is challenging, in particular for scale-free networks with power-law degrees. We present a robust assessment of complex networks that does not depend on the entire degree distribution, but only on its mean, range, and dispersion: summary statistics that are easy to obtain for most real-world networks. By solving several semi-infinite linear programs, we obtain tight (the sharpest possible) bounds for correlation and clustering measures, for all networks with degree distributions that share the same summary statistics. We identify various extremal random graphs that attain these tight bounds as the graphs with specific three-point degree distributions. We leverage the tight bounds to obtain robust laws that explain how degree-degree correlations and local clustering evolve as a function of node degrees and network size. These robust laws indicate that power-law networks with diverging variance are among the most extreme networks in terms of correlation and clustering, building a further theoretical foundation for the widely reported scale-free network phenomena such as correlation and clustering decay.

Social diffusion sources can escape detection

Influencing others through social networks is fundamental to all human societies. Whether this happens through the diffusion of rumors, opinions, or viruses, identifying the diffusion source (i.e., the person that initiated it) is a problem that has attracted much research interest. Nevertheless, existing literature has ignored the possibility that the source might strategically modify the network structure (by rewiring links or introducing fake nodes) to escape detection. Here, without restricting our analysis to any particular diffusion scenario, we close this gap by evaluating two mechanisms that hide the source-one stemming from the source's actions, the other from the network structure itself. This reveals that sources can easily escape detection, and that removing links is far more effective than introducing fake nodes. Thus, efforts should focus on exposing concealed ties rather than planted entities; such exposure would drastically improve our chances of detecting the diffusion source.

Link Prediction on Complex Networks: An Experimental Survey

Complex networks have been used widely to model a large number of relationships. The outbreak of COVID-19 has had a huge impact on various complex networks in the real world, for example global trade networks, air transport networks, and even social networks, known as racial equality issues caused by the spread of the epidemic. Link prediction plays an important role in complex network analysis in that it can find missing links or predict the links which will arise in the future in the network by analyzing the existing network structures. Therefore, it is extremely important to study the link prediction problem on complex networks. There are a variety of techniques for link prediction based on the topology of the network and the properties of entities. In this work, a new taxonomy is proposed to divide the link prediction methods into five categories and a comprehensive overview of these methods is provided. The network embedding-based methods, especially graph neural network-based methods, which have attracted increasing attention in recent years, have been creatively investigated as well. Moreover, we analyze thirty-six datasets and divide them into seven types of networks according to their topological features shown in real networks and perform comprehensive experiments on these networks. We further analyze the results of experiments in detail, aiming to discover the most suitable approach for each kind of network.

A complex network model for a society with socioeconomic classes

People's attitudes and behaviors are partially shaped by the socioeconomic class to which they belong. In this work, a model of scale-free graph is proposed to represent the daily personal contacts in a society with three social classes. In the model, the probability of having a connection between two individuals depends on their social classes and on their physical distance. Numerical simulations are performed by considering sociodemographic data from France, Peru, and Zimbabwe. For the complex networks built for these three countries, average values of node degree, shortest-path length, clustering coefficient, closeness centrality, betweenness centrality, and eigenvector centrality are computed. These numerical results are discussed by taking into account the propagation of information about COVID-19.

How does homophily shape the topology of a dynamic network?

We consider a dynamic network of individuals that may hold one of two different opinions in a two-party society. As a dynamical model, agents can endlessly create and delete links to satisfy a preferred degree, and the network is shaped by homophily, a form of social interaction. Characterized by the parameter J∈[-1,1], the latter plays a role similar to Ising spins: agents create links to others of the same opinion with probability (1+J)/2 and delete them with probability (1-J)/2. Using Monte Carlo simulations and mean-field theory, we focus on the network structure in the steady state. We study the effects of J on degree distributions and the fraction of cross-party links. While the extreme cases of homophily or heterophily (J=±1) are easily understood to result in complete polarization or anti-polarization, intermediate values of J lead to interesting features of the network. Our model exhibits the intriguing feature of an "overwhelming transition" occurring when communities of different sizes are subject to sufficient heterophily: agents of the minority group are oversubscribed and their average degree greatly exceeds that of the majority group. In addition, we introduce an original measure of polarization which displays distinct advantages over the commonly used average edge homogeneity.

Inferring the connectivity of coupled chaotic oscillators using Kalman filtering

Inferring the interactions between coupled oscillators is a significant open problem in complexity science, with multiple interdisciplinary applications. While the Kalman filter (KF) technique is a well-known tool, widely used for data assimilation and parameter estimation, to the best of our knowledge, it has not yet been used for inferring the connectivity of coupled chaotic oscillators. Here we demonstrate that KF allows reconstructing the interaction topology and the coupling strength of a network of mutually coupled Rössler-like chaotic oscillators. We show that the connectivity can be inferred by considering only the observed dynamics of a single variable of the three that define the phase space of each oscillator. We also show that both the coupling strength and the network architecture can be inferred even when the oscillators are close to synchronization. Simulation results are provided to show the effectiveness and applicability of the proposed method.

Systematic comparison of graph embedding methods in practical tasks

Network embedding techniques aim to represent structural properties of graphs in geometric space. Those representations are considered useful in downstream tasks such as link prediction and clustering. However, the number of graph embedding methods available on the market is large, and practitioners face the nontrivial choice of selecting the proper approach for a given application. The present work attempts to close this gap of knowledge through a systematic comparison of 11 different methods for graph embedding. We consider methods for embedding networks in the hyperbolic and Euclidean metric spaces, as well as nonmetric community-based embedding methods. We apply these methods to embed more than 100 real-world and synthetic networks. Three common downstream tasks - mapping accuracy, greedy routing, and link prediction - are considered to evaluate the quality of the various embedding methods. Our results show that some Euclidean embedding methods excel in greedy routing. As for link prediction, community-based and hyperbolic embedding methods yield an overall performance that is superior to that of Euclidean-space-based approaches. We compare the running time for different methods and further analyze the impact of different network characteristics such as degree distribution, modularity, and clustering coefficients on the quality of the embedding results. We release our evaluation framework to provide a standardized benchmark for arbitrary embedding methods.

Dose-response functions and surrogate models for exploring social contagion in the Copenhagen Networks Study

Spreading dynamics and complex contagion processes on networks are important mechanisms underlying the emergence of critical transitions, tipping points and other non-linear phenomena in complex human and natural systems. Increasing amounts of temporal network data are now becoming available to study such spreading processes of behaviours, opinions, ideas, diseases and innovations to test hypotheses regarding their specific properties. To this end, we here present a methodology based on dose-response functions and hypothesis testing using surrogate data models that randomise most aspects of the empirical data while conserving certain structures relevant to contagion, group or homophily dynamics. We demonstrate this methodology for synthetic temporal network data of spreading processes generated by the adaptive voter model. Furthermore, we apply it to empirical temporal network data from the Copenhagen Networks Study. This data set provides a physically-close-contact network between several hundreds of university students participating in the study over the course of 3 months. We study the potential spreading dynamics of the health-related behaviour "regularly going to the fitness studio" on this network. Based on a hierarchy of surrogate data models, we find that our method neither provides significant evidence for an influence of a dose-response-type network spreading process in this data set, nor significant evidence for homophily. The empirical dynamics in exercise behaviour are likely better described by individual features such as the disposition towards the behaviour, and the persistence to maintain it, as well as external influences affecting the whole group, and the non-trivial network structure. The proposed methodology is generic and promising also for applications to other temporal network data sets and traits of interest.

Dimension-reduction of dynamics on real-world networks with symmetry

We derive explicit formulae to quantify the Markov chain state-space compression, or lumping, that can be achieved in a broad range of dynamical processes on real-world networks, including models of epidemics and voting behaviour, by exploiting redundancies due to symmetries. These formulae are applied in a large-scale study of such symmetry-induced lumping in real-world networks, from which we identify specific networks for which lumping enables exact analysis that could not have been done on the full state-space. For most networks, lumping gives a state-space compression ratio of up to 10 7 , but the largest compression ratio identified is nearly 10 12 . Many of the highest compression ratios occur in animal social networks. We also present examples of types of symmetry found in real-world networks that have not been previously reported.

Identifying Influential Nodes Using a Shell-Based Ranking and Filtering Method in Social Networks

The main goal in the influence maximization problem (IMP) is to find k minimum nodes with the highest influence spread on the social networks. Since IMP is NP-hard and is not possible to obtain the optimum results, it is considered by heuristic algorithms. Many strategies focus on the power of the influence spread of core nodes to find k influential nodes. Most of the core detection-based methods concentrate on nodes in the highest core and often give the same power for all nodes in the best core. However, some other nodes fairly have the potential to select as seed nodes in other less important cores, because these nodes can play an important role in the diffusion of information among the core nodes with other nodes. Given this fact, this article proposes a new shell-based ranking and filtering method, called shell-based ranking and filtering method (SRFM), for selecting influential seeds with the aim to maximize influence in the network. The proposed algorithm initially selects a set of nodes in different shells. Moreover, a set of the candidate nodes are created, and most of the periphery nodes are removed during a pruning approach to reduce the computational overhead. Therefore, the seed nodes are selected from the candidate nodes set using the role of the bridge nodes. Experimental results in both synthetic and real data sets showed that the proposed SRFM algorithm has more acceptable efficiency in the influence spread and runtime than other algorithms.

LinkPred: a high performance library for link prediction in complex networks

The problem of determining the likelihood of the existence of a link between two nodes in a network is called link prediction. This is made possible thanks to the existence of a topological structure in most real-life networks. In other words, the topologies of networked systems such as the World Wide Web, the Internet, metabolic networks, and human society are far from random, which implies that partial observations of these networks can be used to infer information about undiscovered interactions. Significant research efforts have been invested into the development of link prediction algorithms, and some researchers have made the implementation of their methods available to the research community. These implementations, however, are often written in different languages and use different modalities of interaction with the user, which hinders their effective use. This paper introduces LinkPred, a high-performance parallel and distributed link prediction library that includes the implementation of the major link prediction algorithms available in the literature. The library can handle networks with up to millions of nodes and edges and offers a unified interface that facilitates the use and comparison of link prediction algorithms by researchers as well as practitioners.

Comprehensive influence of topological location and neighbor information on identifying influential nodes in complex networks

Identifying the influential nodes of complex networks is now seen as essential for optimizing the network structure or efficiently disseminating information through networks. Most of the available methods determine the spreading capability of nodes based on their topological locations or the neighbor information, the degree of node is usually used to denote the neighbor information, and the k-shell is used to denote the locations of nodes, However, k-shell does not provide enough information about the topological connections and position information of the nodes. In this work, a new hybrid method is proposed to identify highly influential spreaders by not only considering the topological location of the node but also the neighbor information. The percentage of triangle structures is employed to measure both the connections among the neighbor nodes and the location of nodes, the contact distance is also taken into consideration to distinguish the interaction influence by different step neighbors. The comparison between our proposed method and some well-known centralities indicates that the proposed measure is more highly correlated with the real spreading process, Furthermore, another comprehensive experiment shows that the top nodes removed according to the proposed method are relatively quick to destroy the network than other compared semi-local measures. Our results may provide further insights into identifying influential individuals according to the structure of the networks.

Agent-based evolving network modeling: a new simulation method for modeling low prevalence infectious diseases

Agent-based network modeling (ABNM) simulates each person at the individual-level as agents of the simulation, and uses network generation algorithms to generate the network of contacts between individuals. ABNM are suitable for simulating individual-level dynamics of infectious diseases, especially for diseases such as HIV that spread through close contacts within intricate contact networks. However, as ABNM simulates a scaled-version of the full population, consisting of all infected and susceptible persons, they are computationally infeasible for studying certain questions in low prevalence diseases such as HIV. We present a new simulation technique, agent-based evolving network modeling (ABENM), which includes a new network generation algorithm, Evolving Contact Network Algorithm (ECNA), for generating scale-free networks. ABENM simulates only infected persons and their immediate contacts at the individual-level as agents of the simulation, and uses the ECNA for generating the contact structures between these individuals. All other susceptible persons are modeled using a compartmental modeling structure. Thus, ABENM has a hybrid agent-based and compartmental modeling structure. The ECNA uses concepts from graph theory for generating scale-free networks. Multiple social networks, including sexual partnership networks and needle sharing networks among injecting drug-users, are known to follow a scale-free network structure. Numerical results comparing ABENM with ABNM estimations for disease trajectories of hypothetical diseases transmitted on scale-free contact networks are promising for application to low prevalence diseases.

Network analysis: An indispensable tool for curricula design. A real case-study of the degree on mathematics at the URJC in Spain

Content addition to courses and its subsequent correct sequencing in a study plan or curricula design context determine the success (and, in some cases, the failure) of such study plan in the acquisition of knowledge by students. In this work, we propose a decision model to guide curricular design committees in the tasks of course selection and sequencing in higher education contexts using a novel methodology based on network analysis. In this work, the local and global properties stemming from complex network analysis tools are studied in detail to facilitate the design of the study plan and to ensure its coherence by detecting the communities within a graph, and the local and global centrality of the courses and their dependencies are analyzed, as well as the overlapping subgroups and the functions and different positions among them. The proposed methodology is applied to the study of a real case at the Universidad Rey Juan Carlos.

Measurement error of network clustering coefficients under randomly missing nodes

The measurement error of the network topology caused by missing network data during the collection process is a major concern in analyzing collected network data. It is essential to clarify the error between the properties of an original network and the collected network to provide an accurate analysis of the entire topology. However, the measurement error of the clustering coefficient, which is a fundamental network property, has not been well understood particularly from an analytical perspective. Here we analytically and numerically investigate the measurement error of two types of clustering coefficients, namely, the global clustering coefficient and the network average clustering coefficient, of a network that is randomly missing some proportion of the nodes. First, we derive the expected error of the clustering coefficients of an incomplete network given a set of randomly missing nodes. We analytically show that (i) the global clustering coefficient of the incomplete network has little expected error and that (ii) conversely, the network average clustering coefficient of the incomplete network is underestimated with an expected error that is dependent on a property that is specific to the graph. Then, we verify the analytical claims through numerical simulations using three typical network models, i.e., the Erdős–Rényi model, the Watts–Strogatz model, and the Barabási–Albert model, and the 15 real-world network datasets consisting of five network types. Although the simulation results on the three typical network models suggest that the measurement error of the clustering coefficients on graphs with considerably small clustering coefficients may not behave like the analytical claims, we demonstrate that the simulation results on real-world networks that typically have enough high clustering coefficients sufficiently support our analytical claims. This study facilitates an analytical understanding of the measurement error in network properties due to missing graph data.

Exact Maximal Reduction Of Stochastic Reaction Networks By Species Lumping

MOTIVATION

Stochastic reaction networks are a widespread model to describe biological systems where the presence of noise is relevant, such as in cell regulatory processes. Unfortunately, in all but simplest models the resulting discrete state-space representation hinders analytical tractability and makes numerical simulations expensive. Reduction methods can lower complexity by computing model projections that preserve dynamics of interest to the user.

RESULTS

We present an exact lumping method for stochastic reaction networks with mass-action kinetics. It hinges on an equivalence relation between the species, resulting in a reduced network where the dynamics of each macro-species is stochastically equivalent to the sum of the original species in each equivalence class, for any choice of the initial state of the system. Furthermore, by an appropriate encoding of kinetic parameters as additional species, the method can establish equivalences that do not depend on specific values of the parameters. The method is supported by an efficient algorithm to compute the largest species equivalence, thus the maximal lumping. The effectiveness and scalability of our lumping technique, as well as the physical interpretability of resulting reductions, is demonstrated in several models of signaling pathways and epidemic processes on complex networks.

AVAILABILITY

The algorithms for species equivalence have been implemented in the software tool ERODE, freely available for download from https://www.erode.eu.

The cost structure of influencers' posts: the risk of losing followers

This paper presents an exploratory study of the posting behavior of digital influencers in social participation platforms. As there are different platforms of social participation, we present a taxonomy to unify the different classifications and delimit the scope of our work. Influencers could produce a positive externality of increasing participation by suggesting social causes and government actions they believe in. However, influencers tend to restrict their posts to the domain subject they became popular for. Our goal is to identify the cost structure of posting behavior of influencers, from the desire to post to the actual act of posting. The findings indicate the two key factors influencers consider when posting are (a) the risk of losing followers and (b) the effort required to verify the information. On the other hand, followers indicate they like it when influencers voice their opinion on social causes. These findings are anchored on social influence theory. We also found different factors that motivate/demotivate people to post on social media. We noticed that the factors that will motivate a user to post can either be aroused in him (i.e., already internalized in the person) or can be "planted" in the person (i.e., from outside).

A Semantic Analysis and Community Detection-Based Artificial Intelligence Model for Core Herb Discovery from the Literature: Taking Chronic Glomerulonephritis Treatment as a Case Study

The Traditional Chinese Medicine (TCM) formula is the main treatment method of TCM. A formula often contains multiple herbs where core herbs play a critical therapeutic effect for treating diseases. It is of great significance to find out the core herbs in formulae for providing evidences and references for the clinical application of Chinese herbs and formulae. In this paper, we propose a core herb discovery model CHDSC based on semantic analysis and community detection to discover the core herbs for treating a certain disease from large-scale literature, which includes three stages: corpus construction, herb network establishment, and core herb discovery. In CHDSC, two artificial intelligence modules are used, where the Chinese word embedding algorithm ESSP2VEC is designed to analyse the semantics of herbs in Chinese literature based on the stroke, structure, and pinyin features of Chinese characters, and the label propagation-based algorithm LILPA is adopted to detect herb communities and core herbs in the herbal semantic network constructed from large-scale literature. To validate the proposed model, we choose chronic glomerulonephritis (CGN) as an example, search 1126 articles about how to treat CGN in TCM from the China National Knowledge Infrastructure (CNKI), and apply CHDSC to analyse the collected literature. Experimental results reveal that CHDSC discovers three major herb communities and eighteen core herbs for treating different CGN syndromes with high accuracy. The community size, degree, and closeness centrality distributions of the herb network are analysed to mine the laws of core herbs. As a result, we can observe that core herbs mainly exist in the communities with more than 25 herbs. The degree and closeness centrality of core herb nodes concentrate on the range of [15, 40] and [0.25, 0.45], respectively. Thus, semantic analysis and community detection are helpful for mining effective core herbs for treating a certain disease from large-scale literature.

Mapping flows on sparse networks with missing links

Unreliable network data can cause community-detection methods to overfit and highlight spurious structures with misleading information about the organization and function of complex systems. Here we show how to detect significant flow-based communities in sparse networks with missing links using the map equation. Since the map equation builds on Shannon entropy estimation, it assumes complete data such that analyzing undersampled networks can lead to overfitting. To overcome this problem, we incorporate a Bayesian approach with assumptions about network uncertainties into the map equation framework. Results in both synthetic and real-world networks show that the Bayesian estimate of the map equation provides a principled approach to revealing significant structures in undersampled networks.

Spatial strength centrality and the effect of spatial embeddings on network architecture

For many networks, it is useful to think of their nodes as being embedded in a latent space, and such embeddings can affect the probabilities for nodes to be adjacent to each other. In this paper, we extend existing models of synthetic networks to spatial network models by first embedding nodes in Euclidean space and then modifying the models so that progressively longer edges occur with progressively smaller probabilities. We start by extending a geographical fitness model by employing Gaussian-distributed fitnesses, and we then develop spatial versions of preferential attachment and configuration models. We define a notion of "spatial strength centrality" to help characterize how strongly a spatial embedding affects network structure, and we examine spatial strength centrality on a variety of real and synthetic networks.

Community Detection in Social Networks Using Affinity Propagation with Adaptive Similarity Matrix

Community detection problem is a projection of data clustering where the network's topological properties are only considered for measuring similarities among nodes. Also, finding communities' kernel nodes and expanding a community from kernel will certainly help us to find optimal communities. Among the existing community detection approaches, the affinity propagation (AP)-based method has been showing promising results and does not require any predefined information such as the number of clusters (communities). AP is an exemplar-based clustering method that defines the negative real-valued similarity measure sim(i, k) between data point i and exemplar k as the probability of k being the exemplar of data point i. According to our intuition, the value of sim(i, k) should not be identical to sim(k, i). In this study, a new version of AP using an adaptive similarity matrix, namely affinity propagation with adaptive similarity (APAS) matrix, is proposed, which could efficiently show the leadership probabilities between data points. APAS can adaptively transform the symmetric similarity matrix into an asymmetric one. It outperforms AP method in terms of accuracy. Extensive experiments conducted on artificial and real-world networks demonstrate the effectiveness of our approach.

A Scalable Similarity-Popularity Link Prediction Method

Link prediction is the task of computing the likelihood that a link exists between two given nodes in a network. With countless applications in different areas of science and engineering, link prediction has received the attention of many researchers working in various disciplines. Considerable research efforts have been invested into the development of increasingly accurate prediction methods. Most of the proposed algorithms, however, have limited use in practice because of their high computational requirements. The aim of this work is to develop a scalable link prediction algorithm that offers a higher overall predictive power than existing methods. The proposed solution falls into the class of global, parameter-free similarity-popularity-based methods, and in it, we assume that network topology is governed by three factors: popularity of the nodes, their similarity and the attraction induced by local neighbourhood. In our approach, popularity and neighbourhood-caused attraction are computed directly from the network topology and factored out by introducing a specific weight map, which is then used to estimate the dissimilarity between non-adjacent nodes through shortest path distances. We show through extensive experimental testing that the proposed method produces highly accurate predictions at a fraction of the computational cost required by existing global methods and at a low additional cost compared to local methods. The scalability of the proposed algorithm is demonstrated on several large networks having hundreds of thousands of nodes.

Identifying vital nodes in complex networks by adjacency information entropy

Identifying the vital nodes in networks is of great significance for understanding the function of nodes and the nature of networks. Many centrality indices, such as betweenness centrality (BC), eccentricity centrality (EC), closeness centricity (CC), structural holes (SH), degree centrality (DC), PageRank (PR) and eigenvector centrality (VC), have been proposed to identify the influential nodes of networks. However, some of these indices have limited application scopes. EC and CC are generally only applicable to undirected networks, while PR and VC are generally used for directed networks. To design a more applicable centrality measure, two vital node identification algorithms based on node adjacency information entropy are proposed in this paper. To validate the effectiveness and applicability of the proposed algorithms, contrast experiments are conducted with the BC, EC, CC, SH, DC, PR and VC indices in different kinds of networks. The results show that the index in this paper has a high correlation with the local metric DC, and it also has a certain correlation with the PR and VC indices for directed networks. In addition, the experimental results indicate that our algorithms can effectively identify the vital nodes in different networks.

Modeling Citation Trajectories of Scientific Papers

Several network growth models have been proposed in the literature that attempt to incorporate properties of citation networks. Generally, these models aim at retaining the degree distribution observed in real-world networks. In this work, we explore whether existing network growth models can realize the diversity in citation growth exhibited by individual papers – a new node-centric property observed recently in citation networks across multiple domains of research. We theoretically and empirically show that the network growth models which are solely based on degree and/or intrinsic fitness cannot realize certain temporal growth behaviors that are observed in real-world citation networks. To this end, we propose two new growth models that localize the influence of papers through an appropriate attachment mechanism. Experimental results on the real-world citation networks of Computer Science and Physics domains show that our proposed models can better explain the temporal behavior of citation networks than existing models.

Distance perception warped by social relations: Social interaction information compresses distance

Though distance perception feeds the fundamental input that constructs a visual structure of the world, the suggestion has been made that it is constrained by this constructed structure. Instead of focusing on the physically defined structure, this study investigates whether and how social relations, especially the quality of social interaction (how individuals interact) rather than its content (what type of social interaction), precisely influences distance perception. The quality of social interaction was framed as an actor's intent and incurred outcome regarding another individual, whether helpful or harmful. Through visual animations, intent was operationalized as an agent's (i.e., actor's) intentional or unintentional act having an influence on another agent (i.e., affectee). Two experiments were conducted. In Experiment 1, the act was helpful, resulting in small or great beneficial consequences to the affectee. In Experiment 2, the act was harmful and resulted in small or great losses to the affectee. We found that when the help or harm had a large effect on others (the great-benefits or great-losses conditions), distance was perceived as shorter than when help or harm was minor, and the actor's intent did not affect distance perception. This suggests that, regardless of the type of social interaction, distance perception is mainly influenced by the outcome of an act not by the actor's intent. It implies that the perceived quality of social interaction creates a social constraint on distance perception. These findings are consistent with the idea that the intent and outcome of an action are assessed differently, and they help us understand how social relation penetrates the perceptual system.