结合最大度与最小聚类系数的复杂网络搜索策略研究
|
摘要
复杂网络中的搜索问题涉及网络中指定文件或数据的寻找及网络节点间最短路径的确定,具有重要的现实意义和较高的研究价值。复杂网络搜索策略通常可用一个消息传递的过程来描述,多采用局部搜索方式,其性能将直接影响到能否快速有效地搜索到所需要的目标,以及找到目标所花费的代价能否被接受。实际的复杂网络中普遍同时存在多种拓扑特征,本文从兼顾无标度和小世界特性的角度出发,对局部搜索策略进行了深入的分析、研究和改进。
本文研究了基本的复杂网络拓扑特征、拓扑模型和搜索策略,比较了各种复杂网络搜索策略的优劣,分析了最大度搜索策略的缺陷成因,指出存在一分界值,可使得对于该范围内的节点的搜索过程符合“按度序列搜索”的设想,保证最大度搜索策略的高效。基于分界值,本文提出了将复杂网络中的节点按其度的大小分为两部分的思想,对度小于分界值的那一部分节点采用最大度搜索策略,而对度不小于分界值的那一部分节点采用最小聚类系数搜索策略,并设计了结合最大度与最小聚类系数的复杂网络搜索策略。本文完成了对现有的实际复杂网络数据集的分析和处理工作,将包含着网络邻接矩阵的数据集转换成为了存储着网络全部节点的数组,并抽取和计算了节点的相关局部信息,之后实现了最大度搜索策略、最小聚类系数搜索策略、最大—最小度搜索策略及本文提出的结合最大度与最小聚类系数的复杂网络搜索策略的具体搜索过程。
本文使用具有不同复杂网络拓扑特征的数据集,完成了相关的仿真测试工作,并依据平均搜索步数和平均搜索时间这两大有效性指标,比较、分析和评价了各个复杂网络搜索策略的搜索效果,验证了结合最大度与最小聚类系数的复杂网络搜索策略的正确性和有效性。
Search problem in the complex network involved in finding the specified file or data and determining the shortest path between nodes, has important practical significance and research value. Complex network search strategy, adopted the local search methods, is described as a message transfer process. Its performance will directly affect the ability to search quickly and efficiently and the cost can be accepted. Real complex network generally has a variety of topological characteristics. This paper takes into account the scale-free and small world properties, conducted in-depth analysis, research and improvement of the local search strategies.
In this paper, introduce the basic topological characteristics, topological models and search strategies in the complex network, and then compare them. Analyze the defect causes of high degree seeking. Point out that there is a dividing value, makes the search process conform to imagine of search by degree sequence, to ensure the efficient of high degree seeking. Based on it, propose that divide the complex network into two parts according to node degree. Adopt the maximum degree search strategy for the nodes that degree less than it, and adopt the minimum clustering coefficient search strategy for the nodes that degree not less than it. And then design the complex network search strategy combined with Max degree and Min clustering coefficient. In this paper, complete task that analyze and dispose the existing data sets about real complex network, convert a data set contained adjacency matrix into a array, extract and calculate the relevant local information of node, and then achieve the search process of the maximum degree search strategy, the minimum clustering coefficient search strategy, the maximum-minimum degree search strategy and the complex network search strategy combined with Max degree and Min clustering coefficient.
This article completes the relevant simulation test, used certain data sets with the various complex network topological characteristics. According to the average search steps and the average search time, compare, analyze and evaluate search effect of these complex network search strategy. Verify the correctness and validity of the complex network search strategy combined with Max degree and Min clustering coefficient.
本文研究了基本的复杂网络拓扑特征、拓扑模型和搜索策略,比较了各种复杂网络搜索策略的优劣,分析了最大度搜索策略的缺陷成因,指出存在一分界值,可使得对于该范围内的节点的搜索过程符合“按度序列搜索”的设想,保证最大度搜索策略的高效。基于分界值,本文提出了将复杂网络中的节点按其度的大小分为两部分的思想,对度小于分界值的那一部分节点采用最大度搜索策略,而对度不小于分界值的那一部分节点采用最小聚类系数搜索策略,并设计了结合最大度与最小聚类系数的复杂网络搜索策略。本文完成了对现有的实际复杂网络数据集的分析和处理工作,将包含着网络邻接矩阵的数据集转换成为了存储着网络全部节点的数组,并抽取和计算了节点的相关局部信息,之后实现了最大度搜索策略、最小聚类系数搜索策略、最大—最小度搜索策略及本文提出的结合最大度与最小聚类系数的复杂网络搜索策略的具体搜索过程。
本文使用具有不同复杂网络拓扑特征的数据集,完成了相关的仿真测试工作,并依据平均搜索步数和平均搜索时间这两大有效性指标,比较、分析和评价了各个复杂网络搜索策略的搜索效果,验证了结合最大度与最小聚类系数的复杂网络搜索策略的正确性和有效性。
Search problem in the complex network involved in finding the specified file or data and determining the shortest path between nodes, has important practical significance and research value. Complex network search strategy, adopted the local search methods, is described as a message transfer process. Its performance will directly affect the ability to search quickly and efficiently and the cost can be accepted. Real complex network generally has a variety of topological characteristics. This paper takes into account the scale-free and small world properties, conducted in-depth analysis, research and improvement of the local search strategies.
In this paper, introduce the basic topological characteristics, topological models and search strategies in the complex network, and then compare them. Analyze the defect causes of high degree seeking. Point out that there is a dividing value, makes the search process conform to imagine of search by degree sequence, to ensure the efficient of high degree seeking. Based on it, propose that divide the complex network into two parts according to node degree. Adopt the maximum degree search strategy for the nodes that degree less than it, and adopt the minimum clustering coefficient search strategy for the nodes that degree not less than it. And then design the complex network search strategy combined with Max degree and Min clustering coefficient. In this paper, complete task that analyze and dispose the existing data sets about real complex network, convert a data set contained adjacency matrix into a array, extract and calculate the relevant local information of node, and then achieve the search process of the maximum degree search strategy, the minimum clustering coefficient search strategy, the maximum-minimum degree search strategy and the complex network search strategy combined with Max degree and Min clustering coefficient.
This article completes the relevant simulation test, used certain data sets with the various complex network topological characteristics. According to the average search steps and the average search time, compare, analyze and evaluate search effect of these complex network search strategy. Verify the correctness and validity of the complex network search strategy combined with Max degree and Min clustering coefficient.
引文
[1]Watts D. J., Strogatz S. H.. Collective dynamics of'small-world'networks. Nature,1998, 393:440-442
[2]Barabasi A.L., Albert R.. Emergence of scaling in random networks. Science,1999,286: 509-512
[3]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社.2006
[4]周俊杰,汪小帆.复杂网络中的搜索.硕士学位论文.2005
[5]Jon Kleinberg. Complex Networks and Decentralized Search Algorithms. http://www.stat.berkeley.edu/-aldous/Networks/icm06.pdf
[6]Yan Ma, Bin Gong, Lida Zou. Resource Discovery Algorithm Based on Small-World Cluster in Hierarchical Grid Computing Environment. IEEE.2008
[7]Ozgur Simsek, David Jensen. Decentralized search in networks using homophily and degree disparity. Nineteenth International Joint Conference on Artificial Intelligence.2005
[8]温巧林,司守奎,任东彦,谢宇鹏.基于最大度和随机游走的混合搜索算法.海军航空工程学院学报.2010年第25卷第5期.2007
[9]Wang X.F., Chen G.. Complex networks:small-world, scale-free and beyond. IEEE Circuits & Systems Magazine 3(1):6-20.2003.
[10]Moura de A P S, Motter A E, Grebogi C. Searching in small-world networks. Phys. Rev. E 68:36106.2003
[11]邓小清,周竹荣,程向荣.基于蚂蚁算法的网格资源发现模型.计算机应用.27(10).2007.10
[12]Zenggang Xiong, Yang Yang, Xuemin Zhang, Fu Chen, Li Liu. Integrating Genetic and Ant Algorithm into P2P Grid Resource Discovery. IEEE.2005
[13]俞峰,吴铁军.复杂动态随机网络最短路径问题研究.浙江大学博士学位论文.2009
[14]路兰,杨洪勇.基于节点度和边权值比率的网络搜索算法.复杂系统与复杂性科学.2009年12月第6卷第4期.2009
[15]Kashif Ali, Suprakash Datta, Mokhtar Aboelaze. Grid resource discovery using small world overlay graphs. CCECE/CCGCEI.2005.5
[16]Lu Liu, Stephen Mackin, Nick Antonopoulos. Small World Architecture For Peer-to-Peer Networks. IEEE/WIC/ACM.2006
[17]吴淑英,陈卫东.一种基于预测的改进的三步搜索算法.计算机应用与软件25(1).2008
[18]王天骄,汀小帆.无标度和加权网络的搜索问题研究.2007
[19]Ruay-Shiung Chang, Min-Shuo Hu. A resource discovery tree using bitmap for grids. Future Generation Computer Systems.2010
[20]张子婧.符合小世界特性的网格资源动态组织机制研究.北京交通大学硕士学位论文.2010
[21]李孔文,顾庆,张尧,陈道蓄.一种基于聚集系数的局部社团划分算法.计算机科学第37卷第7期.2010
[22]黄佳进,王普,钟宁.复杂网络中搜索策略与推荐系统建模研究.北京工业大学博士后学位论文.2009
[23]许峰,毛钢,秦臻.复杂网络特征量度及典型网络模型分析.通信技术.2010年第09期第43卷.2010
[24]章忠志,周水庾,方锦清.复杂网络确定性模型研究的最新进展.复杂系统与复杂性科学.2008年第5卷第4期.2008.12
[25]李金,蒋国平.一种改进的复杂网络搜索算法及其性能分析.南京邮电大学硕士学位论文.2008
[26]Adamic L A., Lukose R M., Puniyani A R, etc.. Search in power-law networks. Phys. Rev. E,64:046135.2001.
[27]Watts D J, Dodds P S, Newman M E J. Identity and search in social networks. Science,296: 1302-1305,2002.
[28]http://www-personal.umich.edu/-mejn/netdata/
[29]吴艾,刘心松,皮建勇,刘克剑.聚集度相关的网络节点搜索算法.http://d.g.wanfangdata.com.cn/Conference_6150473.aspx
[30]赵垄,牛振东.基于节点簇的P2P随机漫步搜索.华南理工大学学报第7期第38卷.2010.7
[31]张连明,许华岚Internet自治系统级拓扑复杂网络特征分析与验证.计算机工程与应用.2010
[32]徐缓,古传杰.对等网络中应用“最大聚集度优先”算法查询信息及其优化.计算机与现代化总第138期.2007
[33]汤大权,贺明科,孟庆崧.基于幂律分布和小世界特性的无结构P2P网络中搜索方法研究.计算机研究与发展.2007
[34]唐敏.聚集系数在对等网路由搜索算法中的应用.信息通信2010(5)
[35]张亮.复杂网络增长模型及社区结构划分方法.大连理工大学硕士学位论文.2008
[36]韦洛霞.复杂网络模型和方法.东莞理工学院学报第11卷第4期.2004
[2]Barabasi A.L., Albert R.. Emergence of scaling in random networks. Science,1999,286: 509-512
[3]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社.2006
[4]周俊杰,汪小帆.复杂网络中的搜索.硕士学位论文.2005
[5]Jon Kleinberg. Complex Networks and Decentralized Search Algorithms. http://www.stat.berkeley.edu/-aldous/Networks/icm06.pdf
[6]Yan Ma, Bin Gong, Lida Zou. Resource Discovery Algorithm Based on Small-World Cluster in Hierarchical Grid Computing Environment. IEEE.2008
[7]Ozgur Simsek, David Jensen. Decentralized search in networks using homophily and degree disparity. Nineteenth International Joint Conference on Artificial Intelligence.2005
[8]温巧林,司守奎,任东彦,谢宇鹏.基于最大度和随机游走的混合搜索算法.海军航空工程学院学报.2010年第25卷第5期.2007
[9]Wang X.F., Chen G.. Complex networks:small-world, scale-free and beyond. IEEE Circuits & Systems Magazine 3(1):6-20.2003.
[10]Moura de A P S, Motter A E, Grebogi C. Searching in small-world networks. Phys. Rev. E 68:36106.2003
[11]邓小清,周竹荣,程向荣.基于蚂蚁算法的网格资源发现模型.计算机应用.27(10).2007.10
[12]Zenggang Xiong, Yang Yang, Xuemin Zhang, Fu Chen, Li Liu. Integrating Genetic and Ant Algorithm into P2P Grid Resource Discovery. IEEE.2005
[13]俞峰,吴铁军.复杂动态随机网络最短路径问题研究.浙江大学博士学位论文.2009
[14]路兰,杨洪勇.基于节点度和边权值比率的网络搜索算法.复杂系统与复杂性科学.2009年12月第6卷第4期.2009
[15]Kashif Ali, Suprakash Datta, Mokhtar Aboelaze. Grid resource discovery using small world overlay graphs. CCECE/CCGCEI.2005.5
[16]Lu Liu, Stephen Mackin, Nick Antonopoulos. Small World Architecture For Peer-to-Peer Networks. IEEE/WIC/ACM.2006
[17]吴淑英,陈卫东.一种基于预测的改进的三步搜索算法.计算机应用与软件25(1).2008
[18]王天骄,汀小帆.无标度和加权网络的搜索问题研究.2007
[19]Ruay-Shiung Chang, Min-Shuo Hu. A resource discovery tree using bitmap for grids. Future Generation Computer Systems.2010
[20]张子婧.符合小世界特性的网格资源动态组织机制研究.北京交通大学硕士学位论文.2010
[21]李孔文,顾庆,张尧,陈道蓄.一种基于聚集系数的局部社团划分算法.计算机科学第37卷第7期.2010
[22]黄佳进,王普,钟宁.复杂网络中搜索策略与推荐系统建模研究.北京工业大学博士后学位论文.2009
[23]许峰,毛钢,秦臻.复杂网络特征量度及典型网络模型分析.通信技术.2010年第09期第43卷.2010
[24]章忠志,周水庾,方锦清.复杂网络确定性模型研究的最新进展.复杂系统与复杂性科学.2008年第5卷第4期.2008.12
[25]李金,蒋国平.一种改进的复杂网络搜索算法及其性能分析.南京邮电大学硕士学位论文.2008
[26]Adamic L A., Lukose R M., Puniyani A R, etc.. Search in power-law networks. Phys. Rev. E,64:046135.2001.
[27]Watts D J, Dodds P S, Newman M E J. Identity and search in social networks. Science,296: 1302-1305,2002.
[28]http://www-personal.umich.edu/-mejn/netdata/
[29]吴艾,刘心松,皮建勇,刘克剑.聚集度相关的网络节点搜索算法.http://d.g.wanfangdata.com.cn/Conference_6150473.aspx
[30]赵垄,牛振东.基于节点簇的P2P随机漫步搜索.华南理工大学学报第7期第38卷.2010.7
[31]张连明,许华岚Internet自治系统级拓扑复杂网络特征分析与验证.计算机工程与应用.2010
[32]徐缓,古传杰.对等网络中应用“最大聚集度优先”算法查询信息及其优化.计算机与现代化总第138期.2007
[33]汤大权,贺明科,孟庆崧.基于幂律分布和小世界特性的无结构P2P网络中搜索方法研究.计算机研究与发展.2007
[34]唐敏.聚集系数在对等网路由搜索算法中的应用.信息通信2010(5)
[35]张亮.复杂网络增长模型及社区结构划分方法.大连理工大学硕士学位论文.2008
[36]韦洛霞.复杂网络模型和方法.东莞理工学院学报第11卷第4期.2004