复杂网络子图中心性分析

许多现实网络虽然具有小世界和无标度的全局结构特征,但可能具有非常不同的局部结构特征,子图从局部层次刻画了网络内部相互连接的特定模式.本文通过仿真分析的方法研究了ER随机网络、WS小世界网络和BA无标度网络模型的子图中心性的特点,得出了这三类网络模型的子图中心性与网络密度、重连概率和网络规模之间的关系.仿真结果表明,子图中心性能够刻画复杂网络的拓扑结构.     

图格的定义与性质研究

本文定义了一种偏序关系将图与格的有关知识联系起来了,给出了图格的定义,并进一步分析和证明了图格的部分性质.     

图的Normalized Laplacian多项式系数

首先利用图的一级半子图给出了Normalized Laplacian特征多项式系数的一个组合表达式,然后在此表达式的基础上,用组合方法证明了Normalized Laplacian谱和图的结构之间的一系列关系式.     

任意基数集上的拟阵的约束

根据Betten和Wenzel于2003年提出的任意基数集上的拟阵的定义,将有限拟阵的约束的概念推广到无限,并讨论此类无限拟阵的约束所具有的性质,最后利用图论知识,定义一个无限拟阵,验证该推广的正确性.     

完全二分图的生成树的个数

给出了生成子图的定义．证明了生成子图的构造定理和计数定理．提出了任意G（p,q）的生成树的计数方法和构造方法．介绍了完全二分图K3,3的生成树的计数和构造．     

几乎三角剖分图中的2—连通支撑子图

证明了每一个无可分离三角形的几乎三角剖分图均存在一个２－连通支撑子图,其最大度至多３．并且,这一结果是最佳可能的。     

一种基于特征子图的不确定图分类算法

采用频繁子图作为特征子图,对不确定图进行分类.提出AGF频繁子图挖掘算法,该算法将频繁子图挖掘问题转换为频繁项挖掘问题,可有效提高频繁子图生成效率.利用频繁子图构造分类模型,首次应用于不确定图,通过实验证明,给出的分类算法具有良好的分类正确率.     

Method for quickly inferring the mechanisms of large-scale complex networks based on the census of subgraph concentrations

A Mechanism-Inferring method of networks exploited from machine learning theory can effectively evaluate the predicting performance of a network model. The existing method for inferring network mechanisms based on a census of subgraph numbers has some drawbacks, especially the need for a runtime increasing strongly with network size and network density. In this paper, an improved method has been proposed by introducing a census algorithm of subgraph concentrations. Network mechanism can be quickly inferred by the new method even though the network has large scale and high density. Therefore, the application perspective of mechanism-inferring method has been extended into the wider fields of large-scale complex networks. By applying the new method to a case of protein interaction network, the authors obtain the same inferring result as the existing method, which approves the effectiveness of the method. This research was supported by the National Natural Science Foundation of China under Grant No. 70401019.     

具有约束的极小生成子图的一个算法

针对实际中的一类连接问题建立了网络模型，给出了便于计算机实现的算法，即：通过依次收缩各边简化网络Ｇ＝ （ Ｖ，Ｅ，Ｗ） ，最终得到最小生成树；然后恢复各边和顶点，从而得到了此类问题的最优解。     

Euler生成子图边数的一个定理

证明了设G=(V,E)是2-边连通的简单图,| V |=n,δ(G)是G的最小度,若δ(G)≥max{4,n-4/5}时,G存在Euler生成子图H,使得| E(H)|/|E(G)|≥2/3;即此时Catlin的2/3--猜想成立.