基于集成学习的复杂网络链路预测及其形成机制分析

为了预测节点与网络中其他现有节点之间的新连接或缺失连接，链路(边)预测近年来引发了越来越多的研究兴趣。最近已经提出各种具有不同特点的算法，以解决链路预测的问题，其中每种算法只考虑一种网络信息，从而产生片面的结果。提出基于集成学习的方法，将所有单一算法集成组合，综合考虑网络的各种信息来解决这一问题。在8个真实网络上进行了实验，利用局部拓扑索引、全局拓扑索引和推荐算法提取了17个不同的特征。结果表明，集成学习的关键性能指标——受试者工作特征曲线 (receiver operating characteristic curve， ROC)下面积(area under curve， AUC)比最佳单一算法提高2%至17%，最高达到0.9624。此外，根据度分布和随机森林得到的特征选择，分析了不同类型网络的结构与形成机制。在形成机制、网络类型和功能之间，获得了一些重要的见解:由某些确定的机制或假设导出的特征，确实是连接2个节点的内在驱动力，也正因为如此，这些特征可以用于链路预测。

Link prediction and analysis of formation mechanism of complex networks based on ensemble learning

To predict new or missing connections between a node and other existing nodes in the network,link (edge) prediction has sparked increasing research interest in recent years. Recently,a variety of algorithms with different characteristics have been proposed to solve the problems of link prediction, for which each algorithm only takes into account a kind of information of the network and thus leads to a one-sided result. We present an ensemble learning method to combine all the single algorithms and take comprehensive account of the most information. An experiment succeeds on eight real networks, in which we extract 17 different features using local topological indexes, global topological indexes and recommended algorithm. The results suggest that AUC of ensemble learning are 2% to 17% higher than the best single algorithms and the highest score can be achieved 0.9624. Furthermore, we analyze the structure and formation mechanism of different types of networks according to the degree distribution and feature selection from random forest. We obtain some significant insights among formation mechanism, network types and features. The features conducted from certain mechanisms or assumptions, are really reflecting the driven force of connection of node pairs, and therefore can be suitably used for link prediction.