资源描述：
《复杂网络中的完全子图搜索算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第27卷第6期增刊仪器仪表学报Vol.27No.62006年6月ChineseJournalofScientificInstrumentJune.20063复杂网络中的完全子图搜索算法研究1,2刘夫云1(桂林电子科技大学机电与交通工程系桂林541004)2(浙江大学现代制造工程研究所杭州310027)摘要现实生活中,许多实际网络中通常包含由若干结点组成的完全子图,一些实际网络甚至是由一些完全子图通过公共节点链接而成的,如何搜索这类网络中的完全子图,是一件很有意义的事情。提出了一种搜索这类特殊复杂网络的完全子图的算法,编制了实现算法的程序,将
2、算法程序应用于机械制造中的产品零部件关系网、中药方剂网等实际的复杂网络,取得了良好的效果。为深入研究这一类型的复杂网络提供了有力的工具。关键词复杂网络完全子图搜索算法Algorithmfordetectingcompletesub2graphincomplexnetwork1,2LiuFuyun1(Dept.ofElectronicMachineryandTransportationEngineering,GuilinUniversityofElectronicTechnology,Guilin541004,China)2(Inst.ofC
3、ontemporaryManufacturingEng.,ZhejiangUniversity,Hangzhou310027,China)AbstractManyrealnetworksalwayscontainsomecompletesub2graphs,somenetworksareevencomposedofcompletesub2graphsthroughtheirpublicnodes.Itwouldbeaveryinterestedthingtodetectcompletesub2graphsofthesenetworks.An
4、algorithmfordetectingcompletesub2graphsincomplexnetworkswaspresented,andthealgorithmwasrealizedthroughprogramming.ThealgorithmwasusedinpartsrelationnetworkofproductandChinesetraditionalmedicinenetwork,itworkswellinbothnetworks.Itwillprovideausefultoolforresearchingcomplexn
5、etworkdeeply.Keywordscomplexnetworkcompletesub2graphdetectingalgorithm复杂网络中的聚类(或社团)就是其中之一。近年来,1引言对这一算法的研究引起了人们极大的兴趣,国外相继[326]有人从事这一方面的研究并取得了一些研究成果。网络是顶点以及边的集合,网络形式的系统在现遗憾的是迄今为止,尚没有一种通用的能搜索所有复实世界的各个领域随处可见。近年来,随着计算技术杂网络的聚类的好算法。的发展,计算能力和存储能力得到很大的提高,使得研在纷繁复杂的各种类型的复杂网络中,有一类很究复杂
6、网络成为可能,因此,国际上兴起了一股研究复特殊的复杂网络,这类网络是由一些完全子图(某些文[1][2][7]杂网络的热潮,并取得了令人瞩目的成果。尽管献又称“固定局域世界”)通过某些公共节点而组成如此,但我们还是可以说,到目前为止,所有这些研究的。现实生活中这种特殊类型的网络随处可见。比较涉及的仅是复杂网络的皮毛,复杂网络尚有许许多多常见的这种类型的网络有:机械制造业中的产品零部未知的内在的规律有待我们进行更深入的研究。寻找件关系网、科学家合作网、电影演员合作网、中药方剂3基金项目:国家自然科学基金资助项目(60374057)926仪器仪表
7、学报第27卷[7]网等等。事实上,所有可用二部图(或二分图)表达成果由哪些科学家共同完成,每个节点归属于完全子的网络类型都可以通过适当的转换而成为由完全子图图的数目则说明某个科学家参与合作项目的数量。电组成的网络。在产品零部件关系网中,以零件作为节影演员合作网中,一个完全子图代表一部电影,完全子点,若干零件构成一个部件,在构成部件的零件中两两图包含的节点数表示这部电影由哪些演员合作演出,连边,从而构成一个完全子图,而不同的部件通过共有每个节点归属于的完全子图的数目表示某个演员演了的零件构成整个网络。在科学家合作网中,以科学家几部电影。在中药
8、方剂网中,完全子图代表一方中药,为节点,如果若干科学家合作写了一篇论文(或合作一完全子图包含的节点数代表该方中药由哪几味药材组项科研项目),则在代表这些科学家的节点间两两连成,每
