加权网络权重自相似评判函数及其社团结构检测

提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.     

An efficient agent-based algorithm for overlapping community detection using nodes’ closeness

Communities are groups of nodes forming tightly connected units in networks. Some nodes can be shared between different communities of a network. The presence of overlapping nodes and their associated membership diversity is a common characteristic of social networks. Analyzing these overlapping structures can reveal valuable information about the intrinsic features of realistic complex networks, especially social networks.     

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

Social power and opinion formation in complex networks

In this paper we investigate the effects of social power on the evolution of opinions in model networks as well as in a number of real social networks. A continuous opinion formation model is considered and the analysis is performed through numerical simulation. Social power is given to a proportion of agents selected either randomly or based on their degrees. As artificial network structures, we consider scale-free networks constructed through preferential attachment and Watts–Strogatz networks. Numerical simulations show that scale-free networks with degree-based social power on the hub nodes have an optimal case where the largest number of the nodes reaches a consensus. However, given power to a random selection of nodes could not improve consensus properties. Introducing social power in Watts–Strogatz networks could not significantly change the consensus profile.     

A weight’s agglomerative method for detecting communities in weighted networks based on weight’s similarity

This paper proposes the new definition of the community structure of the weighted networks that groups of nodes in which the edge's weights distribute uniformly but at random between them. It can describe the steady connections between nodes or some similarity between nodes' functions effectively. In order to detect the community structure efficiently, a threshold coefficient κ to evaluate the equivalence of edges' weights and a new weighted modularity based on the weight's similarity are proposed. Then, constructing the weighted matrix and using the agglomerative mechanism, it presents a weight's agglomerative method based on optimizing the modularity to detect communities. For a network with n nodes, the algorithm can detect the community structure in time O(n²log₂ⁿ). Simulations on networks show that the algorithm has higher accuracy and precision than the existing techniques. Furthermore, with the change of κ the algorithm discovers a special hierarchical organization which can describe the various steady connections between nodes in groups.     

利用邻域“结构洞”寻找社会网络中最具影响力节点

识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.     

The spreading of opposite opinions on online social networks with authoritative nodes

The study of opinion dynamics, such as spreading and controlling of rumors, has become an important issue on social networks. Numerous models have been devised to describe this process, including epidemic models and spin models, which mainly focus on how opinions spread and interact with each other, respectively. In this paper, we propose a model that combines the spreading stage and the interaction stage for opinions to illustrate the process of dispelling a rumor. Moreover, we set up authoritative nodes, which disseminate positive opinion to counterbalance the negative opinion prevailing on online social networking sites. With analysis of the relationship among positive opinion proportion, opinion strength and the density of authoritative nodes in networks with different topologies, we demonstrate that the positive opinion proportion grows with the density of authoritative nodes until the positive opinion prevails in the entire network. In particular, the relationship is linear in homogeneous topologies. Besides, it is also noteworthy that initial locations of the negative opinion source and authoritative nodes do not influence positive opinion proportion in homogeneous networks but have a significant impact on heterogeneous networks. The results are verified by numerical simulations and are helpful to understand the mechanism of two different opinions interacting with each other on online social networking sites.     

Detecting local community structures in complex networks based on local degree central nodes

Detecting local communities in real-world graphs such as large social networks, web graphs, and biological networks has received a great deal of attention because obtaining complete information from a large network is still difficult and unrealistic nowadays. In this paper, we define the term local degree central node whose degree is greater than or equal to the degree of its neighbor nodes. A new method based on the local degree central node to detect the local community is proposed. In our method, the local community is not discovered from the given starting node, but from the local degree central node that is associated with the given starting node. Experiments show that the local central nodes are key nodes of communities in complex networks and the local communities detected by our method have high accuracy. Our algorithm can discover local communities accurately for more nodes and is an effective method to explore community structures of large networks.     

基于区域密度曲线识别网络上的多影响力节点

复杂网络多影响力节点的识别可以帮助理解网络的结构和功能,具有重要的理论意义和应用价值.本文提出一种基于网络区域密度曲线的多影响力节点的识别方法.应用两种不同的传播模型,在不同网络上与其他中心性指标进行了比较.结果表明,基于区域密度曲线的识别方法能够更好地识别网络中的多影响力节点,选中的影响力节点之间的分布较为分散,自身也比较重要.本文所提方法是基于网络的局部信息,计算的时间复杂度较低.     

Properties of asymmetrically evolved community networks

This paper studies a simple asymmetrically evolved community network with a combination of preferential attachment and random properties. An important issue about community networks is to discover the different utility increments of two nodes, where the utility is introduced to investigate the asymmetrical effect of connecting two nodes. On the other hand, the connection of two nodes in community networks can be classified as two nodes belonging to the same or to different communities. The simulation results show that the model can reproduce a power-law utility distribution P(u)～u^-σ, σ = 2 + 1/p, which can be obtained by using mean-field approximation methods. Furthermore, the model exhibits exponential behaviour with respect to small values of a parameter denoting the random effect in our model at the low-utility region and a power-law feature with respect to big values of this parameter at the high-utility region, which is in good agreement with theoretical analysis. This kind of community network can reproduce a unique utility distribution by theoretical and numerical analysis.     

社交网络中基于贝叶斯和半环代数模型的节点影响力计算机理

本文综合考虑网络结构及节点间的互动等关键因素, 提出了一种节点影响力分布式计算机理. 首先根据节点交互行为在时域上的自相似特性, 运用带折扣因子的贝叶斯模型计算节点间的直接影响力; 然后运用半环模型来分析节点间接影响力的聚合; 最后根据社交网络的小世界性质及传播门限, 综上计算出节点的综合影响力. 仿真结果表明, 本文给出的模型能有效抑制虚假粉丝导致的节点影响力波动, 消除了虚假粉丝的出现对节点影响力计算带来的干扰, 从中选择影响力高的若干节点作为传播源节点, 可以将信息传播到更多数目的节点, 促进了信息在社交网络中的传播. 关键词： 社交网络 影响力 贝叶斯 半环代数     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

Computing Influential Nodes Using the Nearest Neighborhood Trust Value and PageRank in Complex Networks

Computing influential nodes gets a lot of attention from many researchers for information spreading in complex networks. It has vast applications, such as viral marketing, social leader creation, rumor control, and opinion monitoring. The information-spreading ability of influential nodes is greater compared with other nodes in the network. Several researchers proposed centrality measures to compute the influential nodes in a complex network, such as degree, betweenness, closeness, semi-local centralities, and PageRank. These centrality methods are defined based on the local and/or global information of nodes in the network. However, due to their high time complexity, centrality measures based on the global information of nodes have become unsuitable for large-scale networks. Very few centrality measures exist that are based on the attributes between nodes and the structure of the network. We propose the nearest neighborhood trust PageRank (NTPR) based on the structural attributes of neighbors and nearest neighbors of nodes. We define the measure based on the degree ratio, the similarity between nodes, the trust values of neighbors, and the nearest neighbors. We computed the influential nodes in various real-world networks using the proposed centrality method. We found the maximum influence by using influential nodes with SIR and independent cascade methods. We also compare the maximum influence of our centrality measure with the existing basic centrality measures.     

Stochastic epidemics and rumours on finite random networks

In this paper, we investigate the stochastic spread of epidemics and rumours on networks. We focus on the general stochastic (SIR) epidemic model and a recently proposed rumour model on networks in Nekovee et al. (2007) [3], and on networks with different random structures, taking into account the structure of the underlying network at the level of the degree–degree correlation function. Using embedded Markov chain techniques and ignoring density correlations between neighbouring nodes, we derive a set of equations for the final size of the epidemic/rumour on a homogeneous network that can be solved numerically, and compare the resulting distribution with the solution of the corresponding mean-field deterministic model. The final size distribution is found to switch from unimodal to bimodal form (indicating the possibility of substantial spread of the epidemic/rumour) at a threshold value that is higher than that for the deterministic model. However, the difference between the two thresholds decreases with the network size, n, following a n^−1/3 behaviour. We then compare results (obtained by Monte Carlo simulation) for the full stochastic model on a homogeneous network, including density correlations at neighbouring nodes, with those for the approximating stochastic model and show that the latter reproduces the exact simulation results with great accuracy. Finally, further Monte Carlo simulations of the full stochastic model are used to explore the effects on the final size distribution of network size and structure (using homogeneous networks, simple random graphs and the Barabasi–Albert scale-free networks).     

Generating weighted community networks based on local events

Many realistic networks have community structures, namely, a network consists of groups of nodes within which links are dense but among which links are sparse. This paper proposes a growing network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Also, it utilizes the preferential attachment for building connections determined by nodes' strengths, which evolves dynamically during the growth of the system. The resulting network reflects the intrinsic community structure with generalized power-law distributions of nodes' degrees and strengths.     

Scaling and correlations in three bus-transport networks of China

We report the statistical properties of three bus-transport networks (BTN) in three different cities of China. These networks are composed of a set of bus lines and stations serviced by these. Network properties, including the degree distribution, clustering and average path length are studied in different definitions of network topology. We explore scaling laws and correlations that may govern intrinsic features of such networks. Besides, we create a weighted network representation for BTN with lines mapped to nodes and number of common stations to weights between lines. In such a representation, the distributions of degree, strength and weight are investigated. A linear behavior between strength and degree s(k)∼k$s(k)\sim k$ is also observed.     

Two-population dynamics in a growing network model

We introduce a growing network evolution model with nodal attributes. The model describes the interactions between potentially violent V and non-violent N agents who have different affinities in establishing connections within their own population versus between the populations. The model is able to generate all stable triads observed in real social systems. In the framework of rate equations theory, we employ the mean-field approximation to derive analytical expressions of the degree distribution and the local clustering coefficient for each type of nodes. Analytical derivations agree well with numerical simulation results. The assortativity of the potentially violent network qualitatively resembles the connectivity pattern in terrorist networks that was recently reported. The assortativity of the network driven by aggression shows clearly different behavior than the assortativity of the networks with connections of non-aggressive nature in agreement with recent empirical results of an online social system.     

Network evolution by nonlinear preferential rewiring of edges

The mathematical framework for small-world networks proposed in a seminal paper by Watts and Strogatz sparked a widespread interest in modeling complex networks in the past decade. However, most of research contributing to static models is in contrast to real-world dynamic networks, such as social and biological networks, which are characterized by rearrangements of connections among agents. In this paper, we study dynamic networks evolved by nonlinear preferential rewiring of edges. The total numbers of vertices and edges of the network are conserved, but edges are continuously rewired according to the nonlinear preference. Assuming power-law kernels with exponents α and β, the network structures in stationary states display a distinct behavior, depending only on β. For β>1, the network is highly heterogeneous with the emergence of starlike structures. For β<1, the network is widely homogeneous with a typical connectivity. At β=1, the network is scale free with an exponential cutoff.     

On the degree distribution of projected networks mapped from bipartite networks

Many real-world systems can be represented by bipartite networks. In a bipartite network, the nodes are divided into two disjoint sets, and the edges connect nodes that belong to different sets. Given a bipartite network (i.e. two-mode network) it is possible to construct two projected networks (i.e. one-mode networks) where each one is composed of only one set of nodes. While network analyses have focused on unipartite networks, considerably less attention has been paid to the analytical study of bipartite networks. Here, we analytically derive simple mathematical relationships that predict degree distributions of the projected networks by only knowing the structure of the original bipartite network. These analytical results are confirmed by computational simulations using artificial and real-world bipartite networks from a variety of biological and social systems. These findings offer in our view new insights into the structure of real-world bipartite networks.     

New network architecture for stoichiometrically,thermodynamically and kinetically balanced metabolic reaction systems

The conventional way of assembling the metabolic reactions into networks by placing the metabolites on the nodes and associating the edges with reactions is shown to violate the mass balance, thermodynamics and kinetics. A new type of metabolic networks referred to as reaction route (RR) networks is discussed. The distinct feature of the RR networks is that both the nodes and edges are subject to mass balance, thermodynamic and kinetic constraints. To satisfy these constraints, it is necessary to introduce two different types of nodes. One of these, referred to as terminal nodes, satisfy the mass balance conditions for external metabolites. The other type of nodes, referred to as intermediate nodes, satisfy the quasi steady-state conditions for internal metabolites. It is further required that every cycle in the network be thermodynamically consistent in that the sum of affinities (Gibbs free energy changes) of the reactions comprising the cycle should add up to zero. A balanced RR metabolic network possesses a remarkable property, namely, every conceivable walk between two terminal nodes involves a sequence of metabolic reaction steps that produce an overall reaction (OR), i.e., a reaction comprising only external metabolites. A key result is that many metabolic reaction networks may be balanced if and only if the network is allowed to be infinite and periodic.