基于搜索效率的复杂网络多模型并行演化分析  

Analysis of parallel evolution of multiple complex network models based on search efficiency

作　　者：吕天阳[1,2,3] 黄少滨[1] 朴秀峰[1] 高坤[1] 贾烨然[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]清华大学计算机科学与技术系,北京100084 [3]中华人民共和国审计署审计科研所,北京100830

出　　处：《中国科学：物理学、力学、天文学》2013年第2期159-166,共8页Scientia Sinica Physica,Mechanica & Astronomica

基　　金：国家自然科学基金(批准号:60903080,60093009);国家科技支撑计划(编号:2009BAH42B02,2012BAH08B02);博士后科学基金(编号:2012M510480);中央高校基本科研业务费专项资金(编号:HEUCFZ1212,HEUCFT1208)资助项目

摘　　要：很多真实的复杂网络呈现无标度性.但是,这些网络为什么在增长过程中遵从优先连接规则?现有研究尚未给出有力的解释.一个合理的猜想是:这些网络如果不遵从优先连接规则,则将处于不利的地位.为证实这一猜想,采用搜索效率作为评价指标,量化评价不同演化模型的优劣.首先提出一种新的复杂网络并行演化模式,使得同一网络中不同的局部遵从不同的演化模型,从而在统一的基础上比较不同演化模型搜索效率的优劣.以BA无标度网络、WS小世界网络和随机网络为基础,构建了异质复杂网络.其次,采用随机游走搜索策略和DS最大度搜索策略,比较遵从不同演化模型的异质子网的搜索效率,力图解释复杂网络中演化模式同质化的原因.实验发现一种"信息壁垒"现象,即处于劣势的网络模型,其所属节点很难被其他模型的节点访问到.实验结果表明:对于以搜索为重要功能的复杂网络,无标度网络具有最强的适应性,从而在一定程度上解释了无标度现象在众多现实复杂网络中存在的原因.Many real complex networks present the scale-free property. However, why do these networks comply with the preferential attachment rule in their growing？ The existing studies have not stated a powerful explanation yet. A reasonable hypothesis is that： if a network fails to comply with the rule of preferential attachment, it will be at a disadvantage in its competition with the other networks. In order to verify this hypothesis, we adopt searching efficiency as a criterion to quantitatively evaluate different evolutionary models. First, the paper proposes a new parallel evolution model of complex network, ensuring that different sub-networks in the same network comply with different evolutionary model. Therefore, we can compare the search efficiency of different evolution models on a uniform basis. We construct the heterogeneous complex network based on BA scale-free network, WS small world network and ER random network. Second, random walk search strategy and DS maximum degree search strategy are applied to compare the search efficiency of the different evolutionary models and to explain the homogenization of the evolution model in a complex network. The ＂Information Barrier＂ phenomenon is found, that is the nodes of a disadvantage network model are difficult to be accessed by the nodes of other models. The experimental results show that： scale-free network is the most adaptive model for searching. This conclusion explains the existence of scale-free phenomenon in many real complex networks to some extent.

关 键 词：复杂网络演化 异质 搜索效率 

分 类 号：O157.5[理学—数学]