Identifying missing and spurious connections via the bi-directional diffusion on bipartite networks

Link prediction and spurious link detection in complex networks have attracted increasing attention from both physical and computer science communities, due to their wide applications in many real systems. Related previous works mainly focus on monopartite networks while these problems in bipartite networks are not yet systematically addressed. Containing two different kinds of nodes, bipartite networks are essentially different from monopartite networks, especially in node similarity calculation: the similarity between nodes of different kinds (called inter-similarity) is not well defined. In this letter, we employ the local diffusion processes to measure the inter-similarity in bipartite networks. We find that the inter-similarity is asymmetric if the diffusion is applied in different directions. Accordingly, we propose a bi-directional hybrid diffusion method which is shown to achieve higher accuracy than the existing diffusion methods in identifying missing and spurious links in bipartite networks.     

TLP-CCC: Temporal Link Prediction Based on Collective Community and Centrality Feature Fusion

In the domain of network science, the future link between nodes is a significant problem in social network analysis. Recently, temporal network link prediction has attracted many researchers due to its valuable real-world applications. However, the methods based on network structure similarity are generally limited to static networks, and the methods based on deep neural networks often have high computational costs. This paper fully mines the network structure information and time-domain attenuation information, and proposes a novel temporal link prediction method. Firstly, the network collective influence (CI) method is used to calculate the weights of nodes and edges. Then, the graph is divided into several community subgraphs by removing the weak link. Moreover, the biased random walk method is proposed, and the embedded representation vector is obtained by the modified Skip-gram model. Finally, this paper proposes a novel temporal link prediction method named TLP-CCC, which integrates collective influence, the community walk features, and the centrality features. Experimental results on nine real dynamic network data sets show that the proposed method performs better for area under curve (AUC) evaluation compared with the classical link prediction methods.     

Deep Link-Prediction Based on the Local Structure of Bipartite Networks

Link prediction based on bipartite networks can not only mine hidden relationships between different types of nodes, but also reveal the inherent law of network evolution. Existing bipartite network link prediction is mainly based on the global structure that cannot analyze the role of the local structure in link prediction. To tackle this problem, this paper proposes a deep link-prediction (DLP) method by leveraging the local structure of bipartite networks. The method first extracts the local structure between target nodes and observes structural information between nodes from a local perspective. Then, representation learning of the local structure is performed on the basis of the graph neural network to extract latent features between target nodes. Lastly, a deep-link prediction model is trained on the basis of latent features between target nodes to achieve link prediction. Experimental results on five datasets showed that DLP achieved significant improvement over existing state-of-the-art link prediction methods. In addition, this paper analyzes the relationship between local structure and link prediction, confirming the effectiveness of a local structure in link prediction.     

Onset of synchronization in weighted complex networks: the effect of weight-degree correlation

By numerical simulations, we investigate the onset of synchronization of networked phase oscillators under two different weighting schemes. In scheme-I, the link weights are correlated to the product of the degrees of the connected nodes, so this kind of networks is named as the weight-degree correlated (WDC) network. In scheme-II, the link weights are randomly assigned to each link regardless of the node degrees, so this kind of networks is named as the weight-degree uncorrelated (WDU) network. Interestingly, it is found that by increasing a parameter that governs the weight distribution, the onset of synchronization in WDC network is monotonically enhanced, while in WDU network there is a reverse in the synchronization performance. We investigate this phenomenon from the viewpoint of gradient network, and explain the contrary roles of coupling gradient on network synchronization: gradient promotes synchronization in WDC network, while deteriorates synchronization in WDU network. The findings highlight the fact that, besides the link weight, the correlation between the weight and the node degree is also important to the network dynamics.     

加权网络中基于冗余边过滤的k-核分解排序算法

k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infectedrecovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层.     

基于层间相似性的时序网络节点重要性研究

时序网络可以更加准确地描述节点之间的交互顺序和交互关系.结合多层耦合网络分析法,本文提出了基于节点层间相似性的超邻接矩阵时序网络节点重要性识别方法,与经典的认为所有层间关系为常数不同,层间关系用节点的邻居拓扑重叠系数进行度量.Workspace和Enrons数据集上的结果显示:相比经典的方法,使用该方法得到的Kendall’sτ值在各时间层上的平均提高,最高为17.72%和12.44%,结果表明层间相似性的度量对于时序网络的节点重要性度量具有十分重要的意义.     

Overlapping Community Detection Based on Membership Degree Propagation

A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.     

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes' attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes' similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recovers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.     

Predicting missing links via local information

Missing link prediction in networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely Common Neighbours, has the best overall performance, and the Adamic-Adar index performs second best. A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbours. It is found that many links are assigned the same scores if only the information of the nearest neighbours is used. We therefore design another new measure exploiting information on the next nearest neighbours, which can remarkably enhance the prediction accuracy.     

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

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

Distinguishing manipulated stocks via trading network analysis

Manipulation is an important issue for both developed and emerging stock markets. For the study of manipulation, it is critical to analyze investor behavior in the stock market. In this paper, an analysis of the full transaction records of over a hundred stocks in a one-year period is conducted. For each stock, a trading network is constructed to characterize the relations among its investors. In trading networks, nodes represent investors and a directed link connects a stock seller to a buyer with the total trade size as the weight of the link, and the node strength is the sum of all edge weights of a node. For all these trading networks, we find that the node degree and node strength both have tails following a power-law distribution. Compared with non-manipulated stocks, manipulated stocks have a high lower bound of the power-law tail, a high average degree of the trading network and a low correlation between the price return and the seller-buyer ratio. These findings may help us to detect manipulated stocks.     

Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.     

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.     

Complex Embedding with Type Constraints for Link Prediction

Large-scale knowledge graphs not only store entities and relations but also provide ontology-based information about them. Type constraints that exist in this information are of great importance for link prediction. In this paper, we proposed a novel complex embedding method, CHolE, in which complex circular correlation was introduced to extend the classic real-valued compositional representation HolE to complex domains, and type constraints were integrated into complex representational embeddings for improving link prediction. The proposed model consisted of two functional components, the type constraint model and the relation learning model, to form type constraints such as modulus constraints and acquire the relatedness between entities accurately by capturing rich interactions in the modulus and phase angles of complex embeddings. Experimental results on benchmark datasets showed that CHolE outperformed previous state-of-the-art methods, and the impartment of type constraints improved its performance on link prediction effectively.     

A time-series approach to measuring node similarity in networks and its application to community detection

A central concept in network analysis is that of similarity between nodes. In this paper, we introduce a dynamic time-series approach to quantifying the similarity between nodes in networks. The problem of measuring node similarity is exquisitely embedded into the framework of time series for state evolution of nodes. We develop a deterministic parameter-free diffusion model to drive the dynamic evolution of node states, and produce a unique time series for each source node. Then we introduce a measure quantifying how far all the other nodes are located from each source one. Following this measure, a quantity called dissimilarity index is proposed to signify the extent of similarity between nodes. Thereof, our dissimilarity index gives a deep and natural integration between the local and global perspectives of topological structure of networks. Furthermore, we apply our dissimilarity index to unveil community structure in networks, which verifies the proposed dissimilarity index.     

Revealing how network structure affects accuracy of link prediction

Link prediction plays an important role in network reconstruction and network evolution. The network structure affects the accuracy of link prediction, which is an interesting problem. In this paper we use common neighbors and the Gini coefficient to reveal the relation between them, which can provide a good reference for the choice of a suitable link prediction algorithm according to the network structure. Moreover, the statistical analysis reveals correlation between the common neighbors index, Gini coefficient index and other indices to describe the network structure, such as Laplacian eigenvalues, clustering coefficient, degree heterogeneity, and assortativity of network. Furthermore, a new method to predict missing links is proposed. The experimental results show that the proposed algorithm yields better prediction accuracy and robustness to the network structure than existing currently used methods for a variety of real-world networks.     

IKN-CF: An Approach to Identify Key Nodes in Inter-Domain Routing Systems Based on Cascading Failures

Inter-domain routing systems is an important complex network in the Internet. Research on the vulnerability of inter-domain routing network nodes is of great support to the stable operation of the Internet. For the problem of node vulnerability, we proposed a method for identifying key nodes in inter-domain routing systems based on cascading failures (IKN-CF). Firstly, we analyzed the topology of inter-domain routing network and proposed an optimal valid path discovery algorithm considering business relationships. Then, the reason and propagation mechanism of cascading failure in the inter-domain routing network were analyzed, and we proposed two cascading indicators, which can approximate the impact of node failure on the network. After that, we established a key node identification model based on improved entropy weight TOPSIS (EWT), and the key node sequence in the network can be obtained through EWT calculation. We compared the existing three methods in two real inter-domain routing networks. The results indicate that the ranking results of IKN-CF are high accuracy, strong stability, and wide applicability. The accuracy of the top 100 nodes of the ranking result can reach 83.6%, which is at least 12.8% higher than the average accuracy of the existing three methods.     

Prediction of sgRNA Off-Target Activity in CRISPR/Cas9 Gene Editing Using Graph Convolution Network

CRISPR/Cas9 is a powerful genome-editing technology that has been widely applied in targeted gene repair and gene expression regulation. One of the main challenges for the CRISPR/Cas9 system is the occurrence of unexpected cleavage at some sites (off-targets) and predicting them is necessary due to its relevance in gene editing research. Very few deep learning models have been developed so far to predict the off-target propensity of single guide RNA (sgRNA) at specific DNA fragments by using artificial feature extract operations and machine learning techniques; however, this is a convoluted process that is difficult to understand and implement for researchers. In this research work, we introduce a novel graph-based approach to predict off-target efficacy of sgRNA in the CRISPR/Cas9 system that is easy to understand and replicate for researchers. This is achieved by creating a graph with sequences as nodes and by using a link prediction method to predict the presence of links between sgRNA and off-target inducing target DNA sequences. Features for the sequences are extracted from within the sequences. We used HEK293 and K562 t datasets in our experiments. GCN predicted the off-target gene knockouts (using link prediction) by predicting the links between sgRNA and off-target sequences with an auROC value of 0.987.     

Identifying influential nodes based on graph signal processing in complex networks

Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However,node heterogeneity(i.e., different attributes such as interest, energy, age, and so on) ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal processing based centrality(GSPC) method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.     

On the Relation between Prediction and Imputation Accuracy under Missing Covariates

Missing covariates in regression or classification problems can prohibit the direct use of advanced tools for further analysis. Recent research has realized an increasing trend towards the use of modern Machine-Learning algorithms for imputation. This originates from their capability of showing favorable prediction accuracy in different learning problems. In this work, we analyze through simulation the interaction between imputation accuracy and prediction accuracy in regression learning problems with missing covariates when Machine-Learning-based methods for both imputation and prediction are used. We see that even a slight decrease in imputation accuracy can seriously affect the prediction accuracy. In addition, we explore imputation performance when using statistical inference procedures in prediction settings, such as the coverage rates of (valid) prediction intervals. Our analysis is based on empirical datasets provided by the UCI Machine Learning repository and an extensive simulation study.