复杂网络模体挖掘算法研究

发布时间：2018-04-15 04:38

本文选题：复杂网络 + 网络模体　；参考：《昆明理工大学》2016年硕士论文

【摘要】：目前,复杂网络的研究一个热点。在生物信息学领域中,发现一个又一个非常有意义的结论。但它不仅仅在生物信息学领域中广泛应用,还应用在社会学,计算机网络,电子商务等等涉及到网络分析的领域中。有名的“啤酒尿不湿”故事,也是通过对商品销售网络中进行关联规则挖掘得出的。而网络模体又是复杂网络信息挖掘中的一个重要信息之一。因为它能够反映出社区团体的规模及效能。面对动态网络的网络模体挖掘这一问题,本文首先用抽象化,形式化的数学语言来表述该问题。其次,本文分析研究了传统动态网络的网络模体挖掘算法,研究其运行效率,并得出其算法效率低的原因。再提出一种新的高效的动态网络的网络模体挖掘算法。并且提出三个性质从理论上来保证本文所提出的动态网络模体挖掘算法的正确性。再次,根据本文提出的三个性质,设计实现了动态网络模体挖掘新算法。在算法设计中,记录用时间权重信息来描述满足网络模体条件的子图的拓扑结构,和满足网络模体条件的子图的顶点信息,以此来保证网络模体挖掘的完整性。并从理论上分析本文提出的新算法与传统算法的时间复杂度,表明新算法比传统算法效率要高很多。再次,本文通过对于动态网络与静态网络的对比分析得出,静态网络是动态网络的一种特殊情况。从而将动态网络与静态网络的网络模体挖掘建立统一关系。同时还分析得出,只需要将本文提出的动态网络模体挖掘算法做相应的修改就可以应用在静态网络的网络模体挖掘中。最后,通过各种实验来验证前面的结论,即新算法的效率高于传统算法的效率。为此设计了4种实验,分别是：度分布服从均匀分布的网络、度分布服从Poisson分布的网络、度分布服从Power-Law分布的网络以及二分图的网络。
[Abstract]:At present, the research of complex network is a hot spot.In the field of bioinformatics, one after another very meaningful conclusions have been found.But it is not only widely used in the field of bioinformatics, but also in the fields of sociology, computer network, electronic commerce and so on.The famous "Beer diaper" story is also derived by mining association rules in commodity sales networks.Network motif is one of the important information in complex network information mining.Because it reflects the size and effectiveness of community groups.Faced with the problem of dynamic network motif mining, this paper first uses abstract and formal mathematical language to express the problem.Secondly, this paper analyzes and studies the traditional dynamic network motif mining algorithm, studies its running efficiency, and obtains the reason of its low efficiency.A new and efficient algorithm for dynamic network motif mining is proposed.Three properties are proposed to ensure the correctness of the dynamic network motif mining algorithm proposed in this paper.Thirdly, according to the three properties proposed in this paper, a new dynamic network motif mining algorithm is designed and implemented.In the algorithm design, time weight information is used to describe the topological structure of the subgraph satisfying the network motif condition and the vertex information of the subgraph satisfying the network motif condition to ensure the integrity of the network motif mining.The time complexity of the new algorithm and the traditional algorithm is analyzed theoretically, which shows that the new algorithm is much more efficient than the traditional algorithm.Thirdly, through the comparative analysis of dynamic network and static network, it is concluded that static network is a special case of dynamic network.In order to establish a unified relationship between dynamic network and static network network motif mining.At the same time, it is concluded that the dynamic network motif mining algorithm proposed in this paper can be applied to static network motif mining only by modifying it.Finally, experiments are conducted to verify the conclusion that the efficiency of the new algorithm is higher than that of the traditional algorithm.Four kinds of experiments are designed for this purpose: the degree distribution follows the uniform distribution network, the degree distribution service follows the Poisson distribution network, the degree distribution service follows the Power-Law distribution network and the bipartite graph network.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13;O157.5

【相似文献】