利用多级社区中心标签实现大规模图上距离查询

距离查询是图数据挖掘应用中的最基本的操作之一,但是目前的现存查询算法均无法高效处理大规模图数据.针对这个问题,提出建立多级社区中心的标签机制,即首先在原图中将结点按社区划分为多个集合,然后再将各集合中的中心结点建成带权查询子图,经过多次递归操作,最终为各结点建立一个基于社区中心的树状结构标签集,该标签集可以实现利用较短的创建时间和较小的存储代价大幅度提高距离查询的效率.从实验结果可以看出,该方法综合效率明显优于现存的高效算法.     

计算超立方体图电阻距离和Kirchhoff指标的新方法

连通(分子)图G的两个顶点i和j之间的电阻距离为通过用单位电阻来代替G中的每条边而相应构造出的电网络中结点i和j之间的有效电阻。Kirchhoff指标Kf(G)是G中所有的顶点对的电阻距离之和。本文提出一种新的简单方法,利用距离传递性给出了超立方体图的电阻距离和Kirchhoff指标的计算公式。     

无向无权图同构判别算法简

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

无向无权图同构判别算法

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

超媒体系统层次分析

提出了一种利用矩阵对超媒体系统进行层次分析的方法．即利用系统内结点的距离矩阵和变换距离矩阵计算结点的中心性，然后根据每个结点的中心性来判定该结点所处的层次位置，由此得到一个超媒体系统的层次结构     

基于非均匀数据率的无线传感器网络平衡耗能算法

无线传感器网络采用多跳、多对一的数据传输方式,使得网络能量消耗不平衡,基站附近结点通信负荷过重成为"热点","热点"区域的结点往往最先死亡导致网络失效,此时其余结点仍剩余大量能量.为平衡网络的能量消耗,提出了一种基于非均匀数据率的无线传感器路由协议,其核心思想是结点根据结点与基站的距离调整数据率(单位时间内结点产生数据的速率,简称数据率),距离基站越近数据率越低,以节省能量用于通信,距离基站越远数据率越高,以充分利用节点的能量.     

URSI:高效的子图同构查询算法

子图同构查询用于返回数据图中与给定查询图匹配的子图,是图数据管理中的核心问题。如果匹配策略不当、查询结点和数据结点之间大量的冗余枚举以及剪枝策略不当,都会引起查询中的冗余计算问题。本文首先将查询图转化为邻居等价类树并使用过滤条件生成候选区域;其次,通过对候选区域探测将区域中的结点进行排列组合得到结点匹配顺序,并对数据结点进行验证,得到查询图在数据图中的所有匹配的子图;最后给出了基于上述策略的URSI算法,并在真实的数据集上通过实验验证了所提算法的高效性。     

基于核心图增量聚类的复杂网络划分算法改进

基于核心图增量聚类的社团划分算法,设置了一个结点度阈值,利用该阈值在给定网络中筛选核心结点,以这些核心结点构造核心子图,调用GN算法产生社团框架;根据结点与社团的相似度,将除核心结点之外的结点划归到各个社团,经过反复调整各结点的归属,产生网络的社团划分。通过举例说明当度阈值设置不当,筛选出的核心结点所构成的核心子图并不能清晰地构成给定网络的各社团框架,从而严重影响网络的社团划分效率与效果。为此对其进行了改进。文中提出的是一种启发式算法,利用结点的度来逐步产生各社团框架,最后生成各社团。通过在真实网络数据集上测试,说明改进算法是高效的。     

应用相似度测量的图离群点检测方法

针对传统离群点检测方法精确度不高的问题,提出了一种同时基于全局和局部视野综合考虑的离群点检测方法,并将其成功应用于事务图数据集的离群点检测。该方法利用极大公共频繁子图来测量任意两个事务图之间的相似度,提出利用基于公共近邻的裁剪方法对相似矩阵进行裁剪,通过计算数据结点的往返距离得出各个结点的离群值评分,弥补了传统基于稳态分布随机游走的离群点检测方法的缺陷。实验结果表明:该方法在事务图数据离群点检测方面的性能明显优于基于subdue的方法,精确度和错误报警率以及召回率提高了约10%。     

一个Hamilton图形充分性的研究

讨论了特殊的 4k(k >1)个结点的简单图中存在Hamilton回路的充分性 ,并由此提出 :具有 4k个结点的 (2k - 1)正则简单图都是Hamilton图 .     

一种基于代数图论的有限元模型节点排序方法

提出了一种基于有限元模型中节点自由度构造赋权单元团图的方法,根据代数图论的理论,应用赋权单元团图的拉普拉斯矩阵的Fiedler向量,对有限元模型的节点进行排序,以达到减少结构刚度矩阵的半带宽和外形的目的,该方法不但能适用于一般有限元模型,而且适用于包含不同类型单元、具有不同自由度节点的混合节点模型,对于混合节点模型,该方法比基于单元团图的拉普拉斯矩阵的代数图论方法能够取得更加满意的结果,据此编制的前处理程序,可以对任意编号的模型进行优化处理,数值算例结果表明本方法是有效的.     

A distance regular graph of type E1 Ed

In this note, the distance regular graph of type E1 Ed is considered and some characterization of the type graph is given. The results generalize the characterization of tight distance regular graphs.     

四叶图距离矩阵2个最大特征值和的变化

为了能够在任何情况下准确得到四叶图在2种图变换下距离特征值的极值,运用行列式的性质、韦达定理及不等式的放缩,给出了四叶图的2种图变换及上述问题的结果。首先分别给出变换前后3种四叶图距离矩阵、距离拉普拉斯矩阵及距离无符号拉普拉斯矩阵,利用行列式的性质计算得出其特征多项式,由韦达定理判断出3种距离特征多项式正负根的个数,通过不等式的放缩估计出特征值的范围,从而求出2个最大特征值和的范围;其次对变化前后四叶图的3种距离矩阵2个最大特征值的和进行比较。结果显示,四叶图在经过2种变换后2个最大特征值的和是增加的。所得结果为特殊图类距离特征值极值问题提供了研究方法,对分子稳定性问题的研究具有一定的借鉴价值。     

任意图同构判定及其应用

建立了任意图的伴随电路模型,使用电路分析方法求解伴随电路,通过解出的节点电压来确定原图拓扑结构的对应顶点,并由此提出了可应用于任意图的同构判定算法.     

基于图谱归一化编辑距离的聚类算法

图之间的距离度量一直是研究的难点之一。文中提出了一种基于图谱归一化编辑距离的聚类方法。首先利用图的谱方法实现图中点的排序,再用串编辑距离进行两图之间的相似性度量,以此距离构成的不相似矩阵,应用基于矩阵理论的聚类算法实现序列图的聚类研究。考虑到图中点的多少差异,给出归一化串编辑距离的方法解决长短谱序列间距离差异误差问题。实验表明,基于图谱归一化编辑距离的聚类方法是有效的。     

图的广义距离谱

基于一些图参数得到了图G及其线图L(G)广义距离谱半径的上下界,并确定了极值图;然后计算了一些合成图的广义距离谱。     

图的Hamilton性与无符号拉普拉斯距离谱半径

本文利用图及其补图的无符号拉普拉斯距离谱半径分别给出了一个图包含Hamilton路、Hamilton圈以及是Hamilton连通图与泛圈图的充分条件。     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.     

应用最优化选择原则求最短路径及长度

用最优化选择原则,对有向赋权图中的最短路径问题进行了讨论,给出在任意简单有限有向赋权图中求从任一点到指定点间的最短路径长度的数学模型,提出构造一条含弧数最少的最短路径的方法,并推广到简单有限无向赋权图中。     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.