统计网络Motif方法的研究与设计  

Research and design of a statistical way for Motif in Network

作　　者：汪海涛[1] 唐华阳 姜瑛[1] 

机构地区：[1]昆明理工大学云南省计算机技术应用重点实验室,云南昆明650500

出　　处：《云南大学学报（自然科学版）》2015年第6期825-831,共7页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金(61462049)

摘　　要：在分析挖掘一个网络中的信息时,一个非常重要的信息就是统计Motif.现有算法是将原始网络在给定的条件下进行边与顶点转换,再从转换后的网络中找出所有子图,如果子图不满足Motif的要求则删除,存在时间复杂度过高的问题.针对这种情况,提出了一种自底向上的剪枝算法,在不需要经过网络转换的前提下,首先找到最小的符合要求的子图,再推导出更大的子图,而且所找到的每个子图均满足Motif的要求.并通过时间效率分析得出,对于该问题而言,提出的算法优于现有的算法,具有一定的理论研究价值.Motif is a very important information when analysis and mining for network. The exiting algorithm for it is used to transform the edge and vertex in original network under given conditions,and then,find all subgraph and get rid of the subgraph that don＇t follow the Motif require. The new algorithm in this paper is a pruning approach based bottom- up rather than don＇ t using the transformation. First we find all minimum subgraph that follow the Motif require,and then deduce other big subgraph. All subgraph that find use the new algorithm is follow Motif require. And through time efficiency analysis concluded that for this problem,the new algorithm is superior to existing algorithms,has some theoretical research value.

关 键 词：复杂网络 自底向上 子图同构 MOTIF 剪枝 

分 类 号：TP301.52[自动化与计算机技术—计算机系统结构]