基于非负矩阵分解的有向网络半监督社区检测

有向网络上的社区检测是网络科学领域一个重要的课题.针对这一问题,本文提出了一种基于非负矩阵分解的有向网络半监督社区检测算法,首先利用先验信息重构邻接矩阵,然后使用先验信息对节点的社区隶属度进行惩罚,并通过行归一化消除节点度异质性的影响,最后运用交替迭代更新给出了目标函数的求解方法.在真实网络数据上的对比实验验证了算法的有效性,相对于基于非负矩阵分解的现有方法,本文方法能显著提高社区发现的准确性.

有向网络中一种快速的分布式随机算法

本文考虑有向网络上多智能体系统中的分布式优化问题。 其全局目标函数可表示为网络中所有局 部目标函数有限和的形式。 通过利用 Nesterov 动量技巧方法和单循环的方差缩减技术 LSVRG, 本文提出了有向网络中一种快速的分布式随机算法 AB-LSVRG。 对光滑和强凸的目标函数,理 论分析证明所提出的算法可以线性收敛到最优解。 基于分布式逻辑回归问题,数值实验表明本文 所提出的算法与现有的一些分布式算法相比表现效果更好。

基于耦合映像格子的有向网络相继故障

针对现实世界中存在大量的有向网络,根据有向网络中边的有向性,提出适合描述有向网络耦合映像格子(CML)的相继故障模型,利用仿真分析的方法研究了BA无标度有向网络和ER随机图有向网络在该模型作用下的相继故障行为。仿真中,对节点数固定的网络采用蓄意攻击和随机攻击两种策略进行攻击,并记录相关数据。通过对所得数据的分析发现:1)这两类有向网络的相继故障进程比同规模的无向网络要剧烈;2)当网络遭受攻击时,有向网络比无向网络更加脆弱;3)ER随机图网络相继故障发生过程中引起网络相继故障规模增长的4个临界值之间存在线性关系。

一个计算无圈有向网络可靠度的新算法

本文对无圈有向网络的可靠度计算进行了研究。提出了加权有序根树的概念;给出了路径集合的一种特殊排序方法;导出了一个计算无圈有向网络可靠度的拓扑公式。在该公式的基础上提出了一个新的计算无圈有向网络可靠度的不交积和算法,算法可以生成简洁的可靠度表达式,从而可以有效地计算无圈有向网络的可靠度。同时验证了算法的有效性。

基于交叉度的有向网络中心节点识别算法研究

利用K-核分解的方法识别中心节点,被认为在复杂网络重要节点发现中具有特殊的优势。但K-核分解法在有向网络中只能简单地利用节点的出度、入度或者两者之和进行分解,不能区分两者的差异。针对这一问题,将有向网络中出度与入度的概念相结合,提出交叉度(cross degree)的概念;并利用交叉度提出识别有向网络中心节点的C-核分解法。该算法在无向网络中退化为K-核分解法。通过仿真实验和分析,发现该方法既保留K-核方法准确有效的优势,同时还具有较好的区分度,能够较好地识别有向网络中的重要节点。

基于有向网络的双U型装配线平衡实验与分析

针对产品的流水装配线组织设计和装配线平衡问题,提出有向网络新方法。在实验室现有直线型装配线上对产品(车模)进行产品结构分析,并对流水装配进行组织设计,获得了各工序时间和紧前关系,但产线平衡率不高。为提高生产效率,对产品的装配过程建立了数学模型。利用有向加权网络理论计算了模型中优先关系权重,实现了计算机程序计算,并用启发式算法对四驱车模型装配工序重新分配,设计双U型装配线。将U型装配线与现有直线型装配线进行了比较,平衡率提高了9.4%,验证了模型和算法的有效性和优越性,有向网络理论提高了运算效率,并为计算大型装配线平衡问题提供了新的方法。

基于仿射传播的有向网络聚类算法

现有大多数的网络聚类方法都只是针对无向网络,已有的有向网络聚类方法建立在传统聚类算法基础之上,存在着一定的局限性。针对上述问题,提出一种基于仿射传播的有向网络聚类算法,该算法首先采用Sim-Rank作为节点之间的相似度,并将计算得到的结果转换为适应于仿射传播算法的负值;然后将相似度矩阵作为输入,利用具有更好性能的仿射传播算法对有向网络进行聚类。实验结果表明,所提出算法的聚类性能优于其他几种具有代表性的有向网络聚类算法。

关于有向网络容量扩充问题

提出了有向网络最大容量的两种计算方法 ,将杨超等人 ( 1 998)的无向网络容量扩充问题 ,扩展到约束条件含固定费用的有向网络的扩充 。

计算无圈有向网络ST可靠性的一个新方法

本文考虑计算无圈有向网络的ＳＴ可靠性问题（至少存在一条从源点ｓ到汇点ｔ的正常运行道路的概率）。文章引进了深度优先搜索（Ｄｅｐｔｈ－ＦｉｒｓｔＳｅａｒｃｈ）有序根树的概念并提出一个新的计算无圈有向网络ＳＴ可靠性的拓扑公式。以该公式为基础，我们利用ＤＦＳ方法提出一个新的计算无圈有向网络ＳＴ可靠性算法，它能生成简洁的可靠性表达式，进而有效地计算无圈有向网络的ＳＴ可靠性。

基于非对称有向网络的拓扑抽象算法研究

网络规模的扩大导致了路由可扩展性的下降,因此未来的网络将向着分层多域的层次路由体系结构发展.在层次路由中,每个路由域通过拓扑抽象算法对内部拓扑进行汇聚并广播给外部节点,拓扑抽象算法将直接影响到网络的路由性能.本文提出了一种用于非对称有向网络的新型拓扑抽象算法———SHEF算法,该算法结合了面向源的拓扑抽象方法和最小生成树的概念,基于重边优先的准则对非对称的有向网络进行拓扑抽象和汇聚.仿真结果证明,该算法的权值偏差比传统方法减少了75%,较好地解决了路由信息复杂度和准确性之间的矛盾,具有良好的路由性能.

基于三角构成规则的加权有向网络拓扑生成算法

针对加权无向图的网络拓扑模型难以表征真实网络环境下节点间有向性的问题,提出了基于三角构成规则的加权有向网络拓扑生成算法,依据概率优先选择节点的邻居节点进行有向性加边,通过网络边权的动态演化实现节点间的不对称性增长。并利用该算法进行了仿真实验。实验表明,基于三角构成的加权有向网络拓扑算法生成的网络拓扑结构符合真实环境下的网络拓扑结构所体现出来的拓扑特性,同时具有较好的聚类系数可控性。

有向网络的最小流问题及其分枝定界解法

在以人为运动主体的交通网络中,堵塞是经常发生的现象。本文研究的网络最小流是指网络中发生最严重堵塞状态时通过网络的最大流量,它是设计和运行交通网络,特别是紧急疏散网络的重要参数。本文提出了网络饱和流、堵塞流、堵塞截面、最小流等基本概念和定义,证明了有关定理,并提出了求解网络最小流的分枝定界解法。这种方法对于具有良性结构的网络来说是一种有效算法。

基于多重特征向量的有向网络社团结构划分算法

有向网络社团结构的识别对于理解复杂系统的结构特性和动力学特性都有着重要的意义。提出了一种基于拉普拉斯矩阵多重特征向量的有向网络社团结构划分算法,该算法利用有向网络拉普拉斯矩阵的前c个较小特征值所对应的特征向量来划分有向网络的社团结构。在人工数据和实证数据上与模块度的谱优化算法和模拟退火算法做了对比实验。实验结果表明,当社团结构明显时,该算法的归一化互信息指标的值接近于1。当社团结构不明显时,该算法所取得的效果也优于谱优化和模拟退火算法。与这两种算法相比,在实证网络上模块度Q值也可以提高17.28%和19.21%。该文工作对于理解有向网络上拉普拉斯矩阵的多重特征向量与网络的社团结构的关系具有十分重要的意义。

收缩邻居节点集方法求解有向网络的最大流问题

最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流.

具有通信时延和有向网络的多智能体分布式优化

本文对非平衡有向拓扑下一阶多智能体系统的分布式优化问题进行研究.研究的智能体在与邻居的通信过程中都有一个变化的时延.本文的目标是找到使得目标函数f(x)=Σ_(i=1 )/Nfi(xi)最小的智能体的状态.提出了一种基于有向图的拉普拉斯矩阵的零特征值对应的左特征向量和智能体的局部信息的控制器.在这项研究中,去掉了fi(xi)的梯度有界要求,并且不要求网络平衡.在某些假设下,所有智能体都达到相同的状态,同时最小化目标函数Σ_(i=1 )/N fi(xi).最后,通过数值模拟验证了本文的研究结果.

老节点间有相互连接的供应链型有向网络

考虑了有向复杂网络老节点之间相互连接的概率,提出Poisson有向网络模型。发现这类网络节点的到达时间服从Γ-分布,从而,获得度分布的解析表达式。研究表明,Poisson有向网络的稳态平均入度分布和稳态平均出度分布表现为幂律分布,它的出度分布幂律特性受老节点之间相互连接的概率控制,但是入度分布与该概率无关.

计算无圈有向网络可靠度的一个有效算法

利用布尔代数知识和网络的拓扑结构相结合 ,同时采用道路排序的技巧、保持可靠度不变的串并联化简等计算 ,给出了一个计算无圈有向网络

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.

一种有向网络中社团结构划分的启发式算法

复杂网络中的社团发现和探测是当前复杂网络分析领域中的一个热点研究问题,并且具有非常广泛的应用前景。但是,传统的社团划分算法主要以无向、无权网络为对象进行分析,不能够适用于现实世界中更多的有向网络、赋权网络等。以有向网络为研究对象,研究其中的社团划分算法。鉴于前人提出的有向网络中社团划分算法存在着计算时间复杂度问题,引入模拟退火算法对其进行改进,并在改进算法中考虑了节点的网络结构属性。通过对不同规模的计算机生成的有向网络进行算法测试,验证了本文算法的正确性。最后,对一个实际复杂网络进行了社团划分,进一步验证了算法的有效性。

赋模糊权的拟强连通有向网络中的最佳树形图

本文在赋模糊数为弧权的拟强连通有向网络中，建立了根据模糊决策来求解最佳树形图的网络模型，并给出了这一模型的有效算法。