基于NUMA延迟发送的时变图弱连通分量求解

时变图连通分量已经被广泛应用到不同场景,如交通路网建设、推荐系统的信息推送等.然而当前多数连通分量求解方法忽视了NUMA体系结构对计算效率产生的影响,即过高的远程内存访问延迟导致低下的算法执行效率.本文针对时变图的弱连通分量求解问题,提出一种基于NUMA延迟发送的时变图弱连通分量求解方法,它通过合理的数据内存布局,合理控制NUMA节点间的信息交换次数,最大限度减少远程内存访问数量,显著提高了算法执行效率.实验结果表明,该方法的性能明显优于当前流行的图处理系统Ligra和Polymer提供的方法.

基于超立方体弱连通性质的多态网络研究

针对超立方体互联网络可能出现的链路故障以及实现本地化处理的需要,分析了3类已有的子立方体弱连通性质.通过探讨由于不同的维度序列而产生的多种节点集团,提出了基于子立方体弱连通性质的多态网络及其基本特征.仿真实验表明,所提出的多态网络比基于单一维度序列的网络,更能准确地反映实际存在的满足弱连通性质的节点集团.

基于弱连通网络的多自主体系统群集运动

基于二阶自主群体的有向网络,提出一种应用个体局部信息的分布式控制协议。利用Lyapunov稳定性理论研究了自主群体动态行为的稳定性,证明了在弱连通网络拓扑结构中,当系统中所有的自主体都不能获得领航者信息时,所有的自主体能够取得群集运动;假设系统中至少有一个自主体可获得领航者信息时,系统中所有的自主体最终能够收敛于领航者的速度。最后通过一个例子进行仿真实验,验证了所得结论的正确性。

L-双拓扑空间中的几类弱连通分支

借助θ-闭包引入BOs-θ连通分支、WPOs-θ连通分支及POs-θ连通分支等三类弱连通分支概念,并研究其性质。得出弱连通分支的并为最大元1,不同的弱连通分支的并不s-相交等结论。

兼容弱连通簇的AdHoc网络分簇算法

现有分簇算法生成的簇结构都是强连通的单一结构,无法充分利用节点资源。针对该问题,提出一种兼容弱连通簇的分簇算法。定义符合弱连通簇的邻居表结构,并阐述邻居表维护策略,该算法去除簇成员与簇首强连通的条件限制,从而可选择更优的节点作为簇首。分析结果表明,该算法得到的簇结构具有较好的稳定性和持续性。

基于染色的分布式弱连通分量求解算法

社交网络、生物信息网络等链接关系数据呈现爆炸性增加,对亿万个顶点级别的大图处理需求愈加迫切,传统的图算法对单点内存的计算依赖性已经不能满足数据规模急速增长的需求.本文针对图的弱连通分量求解问题,提出了一种快速、可扩展的迭代染色算法CR,并建立了算法的MapReduce模型.最后,在Hadoop平台上,对斯坦福大学社会网络分析实验室提供的四组通联数据进行测试,并和开源的数据挖掘工具箱XRIME提供的算法进行了对比.

无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O(|N|+|E|)。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。

弱连通与拓扑连通

本文首先对简单有向图G=(F,E)的顶点集引入拓扑连通的定义,然后指出弱连通与拓扑连通是等价的,最后给出拓扑连通几个重要性质。

弱θ-连通空间及其性质

给出弱θ-连通空间的概念,证明了弱θ-连通性是拓扑不变性,有限可积性,可遗传性等性质.

连通、弱局部连通、K_(1,P)-约束图的完全圈可扩性

给出了弱局部连通的定义 ,证明了顶点数不少于 3的连通图、弱局部连通图、K1 ,P_约束图是完全圈可扩的 .改进了朱永津、王江鲁 ( 1998)文中关于K1 。

弱哈密顿连通图关于Wiener指数,Harary指数,hyper-Wiener指数的充分条件

对于一个平衡二部图,如果任意两个不同部分的顶点可以由一条哈密顿路连接,那么该平衡二部图称为弱哈密顿连通图。在给出连通的平衡二部图的拓扑指数条件的基础上,利用Wiener指数、Harary指数和hyper-Wiener指数分别给出了平衡二部图是弱哈密顿连通的充分条件。

L-双拓扑空间的θ-连通性

在L-双拓扑空间中,利用-θ闭包引入双-θ连通性、弱配-θ连通性及配-θ连通性等概念,讨论它们之间的关系,给出它们的若干等价刻画,得到了关于它们性质的一系列结果.

L-双拓扑空间的γ-连通性

在L-双拓扑空间中,利用γ-闭包引入双γ-连通性、弱配γ-连通性及配γ-连通性等概念,讨论了它们之间的关系,给出它们之间的若干等价刻画,得到了关于它们性质的一系列结果。

L-双拓扑空间的D_α-层连通性

在L-双拓扑空间中,利用Dα-闭包定义并刻画了几种Dα-层连通性(双Dα-层连通性,弱配Dα-层连通性及配Dα-层连通性),并对它们的性质作了深入的研究.

点集拓扑中的连通性注记

现行的点集拓扑教材中关于局部连通至少有两种定义方式,这两种方式在定义局部连通空间时是一致的,但是在定义某一点的局部连通性时却是有差别的.本文将通过具体的例子指出其中的差异,并建立它们之间的联系.

论传播的分类及其数学模型

本文利用系统经济学的资源位理论,在对申农信息传播模型进行剖析的基础上,提出了传播有效性条件:信息发送者和信息接收者的知识软件的交集非空是实现有效传播的必要条件。利用拓扑传播学方法,建立了单向传播和双向互动传播的一步和n步强连通与弱连通模型。最后论述了在系统经济条件下,传媒是经济系统的构造性元素,这是经济学从牛顿时空观转向爱恩斯坦时空观的必然结果。

单演半群的Γ图

对半群Cayley图的研究是近年来十分活跃的研究领域.定义了半群的Cayley图的一种推广图Γ图,刻画了单演半群的Γ图的结构,给出了单演半群的Γ图弱连通的一个充分必要条件.

故障三维Mesh网络中的容错路由

该文在k—Mesh子网连通概念的基础上提出了三维Mesh网络中局部k—Mesh子网弱连通的概念，证明了局部k—Mesh子网弱连通的三维Mesh网络存在全局连通性。基于局部k—Mesh子网弱连通的三维Mesh网络提出了单播、广播容错路由算法。这些算法提高了容错能力且是基于局部信息的，因而具有很好的实际意义。

弱ω-不连通空间(英文)

一个拓扑空间被称为是弱ω-不连通的,如果它可以表示成可数无限个非空闭集的不交并.在实直线上,已知任何区间都不是弱ω-不连通的.本文证明了两条更一般的结论:(1)任何连通,局部连通,局部可数紧的T2-空间都不是弱ω-不连通的;(2)任何可序化的连通空间都不是弱ω-不连通的.