共查询到20条相似文献,搜索用时 31 毫秒
1.
Predicting missing links via local information 总被引:6,自引:0,他引:6
Tao Zhou Linyuan Lü Yi-Cheng Zhang 《The European Physical Journal B - Condensed Matter and Complex Systems》2009,71(4):623-630
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. 相似文献
2.
Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks.In a previous work [Xu et al. Physica A, 456 294(2016)], we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight,and propose a weighted prediction index based on the contributions of paths, namely weighted path entropy(WPE), to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three other typical weighted indices. 相似文献
3.
In this paper, an optimal resource allocation strategy is proposed to enhance traffic dynamics in complex networks. The network resources are the total node packet-delivering capacity and the total link bandwidth. An analytical method is developed to estimate the overall network capacity by using the concept of efficient betweenness (ratio of algorithmic betweenness and local processing capacity). Three network structures (scale-free, small-world, and random networks) and two typical routing protocols (shortest path protocol and efficient routing protocol) are adopted to demonstrate the performance of the proposed strategy. Our results show that the network capacity is reversely proportional to the average path length for a particular routing protocol and the shortest path protocol can achieve the largest network capacity when the proposed resource allocation strategy is adopted. 相似文献
4.
针对多跳认知无线电网络的多层资源分配问题,提出了协作去耦合方法和跨层联合方法,协作去耦合方法首先单独完成路径选择任务,随后进行信道与功率的博弈分配;跨层联合方法则通过博弈直接对路径、信道、功率三层资源进行同时分配,两种方法都综合考虑网络层、介质访问控制层、物理层的启发原则,引入了节点被干扰度信息和节点主动干扰度信息来辅助路径选择,设计了基于功率允许宽度信息的Boltzmann探索来完成信道与功率选择,设计了长链路和瓶颈链路替换消除机制以进一步提高网络性能,从促进收敛角度,选择序贯博弈并设计了具体的博弈过程,此外还分析了博弈的纳什均衡,讨论了两种算法的复杂度,仿真结果表明,协作去耦合方法和跨层联合方法在成功流数量、流可达速率、发射功耗性能指标上均优于简单去耦合的链路博弈、流博弈方法。 相似文献
5.
6.
Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements 总被引:2,自引:0,他引:2
O. Woolley-Meza C. Thiemann D. Grady J. J. Lee H. Seebens B. Blasius D. Brockmann 《The European Physical Journal B - Condensed Matter and Complex Systems》2011,84(4):589-600
We present a comparative network-theoretic analysis of the two largest global
transportation networks: the worldwide air-transportation network (WAN) and the global
cargo-ship network (GCSN). We show that both networks exhibit surprising statistical
similarities despite significant differences in topology and connectivity. Both networks
exhibit a discontinuity in node and link betweenness distributions which implies that
these networks naturally segregate into two different classes of nodes and links. We
introduce a technique based on effective distances, shortest paths and shortest path trees
for strongly weighted symmetric networks and show that in a shortest path tree
representation the most significant features of both networks can be readily seen. We show
that effective shortest path distance, unlike conventional geographic distance measures,
strongly correlates with node centrality measures. Using the new technique we show that
network resilience can be investigated more precisely than with contemporary techniques
that are based on percolation theory. We extract a functional relationship between node
characteristics and resilience to network disruption. Finally we discuss the results,
their implications and conclude that dynamic processes that evolve on both networks are
expected to share universal dynamic characteristics. 相似文献
7.
In this Letter, the bandwidth resource allocation strategy is considered for traffic systems of complex networks. With a finite resource of bandwidth, an allocation strategy with preference parameter α is proposed considering the links importance. The performance of bandwidth allocation strategy is studied for the local routing protocol and the shortest path protocol. When important links are slightly favored in the bandwidth allocation, the system can achieve the optimal traffic performance for the two routing protocols. For the shortest path protocol, we also give a method to estimate the network traffic capacity theoretically. 相似文献
8.
By revisiting the preferential attachment (PA) mechanism for generating a classical scale-free network, we propose a class of novel preferential attachment similarity indices for predicting future links in evolving networks. Extensive experiments on 14 real-life networks show that these new indices can provide more accurate prediction than the traditional one. Due to the improved prediction accuracy and low computational complexity, these proposed preferential attachment indices can be helpful for providing both instructions for mining unknown links and new insights to understand the underlying mechanisms that drive the network evolution. 相似文献
9.
Jin-Xuan Yang Xiao-Dong Zhang 《The European Physical Journal B - Condensed Matter and Complex Systems》2017,90(8):157
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. 相似文献
10.
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. 相似文献
11.
k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infectedrecovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层. 相似文献
12.
Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features. 相似文献
13.
Link prediction is an important task in the field of network analysis and modeling, and predicts missing links in current networks and new links in future networks. In order to improve the performance of link prediction, we integrate global, local, and quasi-local topological information of networks. Here, a novel stacking ensemble framework is proposed for link prediction in this paper. Our approach employs random forest-based recursive feature elimination to select relevant structural features associated with networks and constructs a two-level stacking ensemble model involving various machine learning methods for link prediction. The lower level is composed of three base classifiers, i.e., logistic regression, gradient boosting decision tree, and XGBoost, and their outputs are then integrated with an XGBoost model in the upper level. Extensive experiments were conducted on six networks. Comparison results show that the proposed method can obtain better prediction results and applicability robustness. 相似文献
14.
评价网络中节点的信息传播影响力对于理解网络结构与网络功能具有重要意义.目前,许多基于最短路径的指标,如接近中心性、介数中心性以及半局部(SP)指标等相继用于评价节点传播影响力.最短路径表示节点间信息传播途径始终选择最优方式,然而实际上网络间的信息传播过程更类似于随机游走,信息的传播途径可以是节点间的任一可达路径,在集聚系数高的网络中,节点的局部高聚簇性有利于信息的有效扩散,若只考虑信息按最优传播方式即最短路径传播,则会低估节点信息传播的能力,从而降低节点影响力的排序精度.综合考虑节点与三步内邻居间的有效可达路径以及信息传播率,提出了一种SP指标的改进算法,即ASP算法.在多个经典的实际网络和人工网络上利用SIR模型对传播过程进行仿真,结果表明ASP指标与度指标、核数指标、接近中心性指标、介数中心性指标以及SP指标相比,可以更精确地对节点传播影响力进行排序. 相似文献
15.
We are developing an optical layer-2s witch network that uses both wavelength-division multiplexing and time-division multiplexing technologies for efficient traffic aggregation in metro networks.For efficient traffic aggregation,path bandwidth control is key because it strongly affects bandwidth efficiency.For this paper,we propose a dynamic time-slot allocation method that uses periodic information of difference values of traffic variation.This method can derive near-optimal allocation with lower computational cost,which enlarges the maximum available network size compared with conventional time-slot allocation methods.Numerical results show that the proposed method enables dynamic path control in 1K-node-scale optical layer-2s witch network,which leads to cost-effective metro networks. 相似文献
16.
This paper proposes a resource allocation scheme for hybrid multiple access involving both orthogonal multiple access and non-orthogonal multiple access (NOMA) techniques. The proposed resource allocation scheme employs multi-agent deep reinforcement learning (MA-DRL) to maximize the sum-rate for all users. More specifically, the MA-DRL-based scheme jointly allocates subcarrier and power resources for users by utilizing deep Q networks and multi-agent deep deterministic policy gradient networks. Meanwhile, an adaptive learning determiner mechanism is introduced into our allocation scheme to achieve better sum-rate performance. However, the above deep reinforcement learning adopted by our scheme cannot optimize parameters quickly in the new communication model. In order to better adapt to the new environment and make the resource allocation strategy more robust, we propose a transfer learning scheme based on deep reinforcement learning (T-DRL). The T-DRL-based scheme allows us to transfer the subcarrier allocation network and the power allocation network collectively or independently. Simulation results show that the proposed MA-DRL-based resource allocation scheme can achieve better sum-rate performance. Furthermore, the T-DRL-based scheme can effectively improve the convergence speed of the deep resource allocation network. 相似文献
17.
Community structure is an important feature in many real-world networks. Many methods and algorithms for identifying communities have been proposed and have attracted great attention in recent years. In this paper, we present a new approach for discovering the community structure in networks. The novelty is that the algorithm uses the strength of the ties for sorting out nodes into communities. More specifically, we use the principle of weak ties hypothesis to determine to what community the node belongs. The advantages of this method are its simplicity, accuracy, and low computational cost. We demonstrate the effectiveness and efficiency of our algorithm both on real-world networks and on benchmark graphs. We also show that the distribution of link strength can give a general view of the basic structure information of graphs. 相似文献
18.
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. 相似文献
19.
Community detection in weighted networks is an important challenge. In this paper, we introduce a local weight ratio scheme for identifying the community structures of weighted networks within the context of the Kuramoto model by taking into account weights of links. The proposed scheme takes full advantage of the information of the link density among vertices and the closeness of relations between each vertex and its neighbors. By means of this scheme, we explore the connection between community structures and dynamic time scales of synchronization. Moreover, we can also unravel the hierarchical structures of weighted networks with a well-defined connectivity pattern by the synchronization process. The performance of the proposed method is evaluated on both computer-generated benchmark graphs and real-world networks. 相似文献
20.
As network data increases, it is more common than ever for researchers to analyze a set of networks rather than a single network and measure the difference between networks by developing a number of network comparison methods. Network comparison is able to quantify dissimilarity between networks by comparing the structural topological difference of networks. Here, we propose a kind of measures for network comparison based on the shortest path distribution combined with node centrality, capturing the global topological difference with local features. Based on the characterized path distributions, we define and compare network distance between networks to measure how dissimilar the two networks are, and the network entropy to characterize a typical network system. We find that the network distance is able to discriminate networks generated by different models. Combining more information on end nodes along a path can further amplify the dissimilarity of networks. The network entropy is able to detect tipping points in the evolution of synthetic networks. Extensive numerical simulations reveal the effectivity of the proposed measure in network reduction of multilayer networks, and identification of typical system states in temporal networks as well. 相似文献