字典乘积网络的支撑树计数

支撑树个数是边失效下网络可靠性分析与设计的一个重要性能参考指标,本文利用字典乘积的方法来构建网络,通过这种方法我们很容易由若干特定规模较小网络来构建规模较大的网络,并得到它的一个紧的支撑树计数解析公式,这样的计数公式仅仅依赖于小网络的性能参数,如:结点的度数、小网络的阶数、小网络的支撑树数目.     

交通网络中线圈布局优化的支撑树算法

从图的拓扑特征角度出发, 提出了一种解决交通网络线圈布局优化问题的支撑树算法。新方法首先通过网络超级变换使得流量守恒条件在变换后网络的所有节点上均成立, 再通过分析一般支撑树的拓扑特征, 从而得到一种解决全网观测最小线圈集位置确定问题的图论方法。新方法具有如下特点：a)避免了复杂的数学分析与运算; b)揭示了安装线圈路段的网络拓扑结构; c)利用支撑树多样性的优势, 可提供多种优化布局方案。最后通过算例验证了该方法的合理性与实用性。     

贝叶斯网络结构学习的简化贪婪算法

基于数据的贝叶斯网络结构学习是一个NP难题.基于条件约束和评分搜索相结合的方法是贝叶斯网络结构学习的一个热点.基于互信息理论提出一种最大支撑树(MWST)机制,并基于最大支撑树结合贪婪搜索的思想提出一种简化贪婪算法.简化贪婪算法不依赖先验知识,完全基于数据集.首先,通过计算互信息建立目标网络的最大支撑树;然后,在最大支撑树的基础上学习初始网络结构,最后,利用简化搜索机制对初始结构进一步优化,最终完成贝叶斯网络的结构学习.数据仿真实验证明,简化贪婪算法不仅具有很高的精度而且具有高效率.     

源路由胖树网络路由生成验证与查询方法研究

路由生成是构建源路由胖树互连网络的重要步骤之一。针对源路由胖树网络路由生成问题,采用面向对象的方法,首先建立胖树网络的拓扑结构模型并提出分段路由方法,接着研究路由生成、正确性验证、路径查询的相关算法,最后探讨路由生成验证与查询软件的设计与实现。目前,该软件已经成功应用于多个源路由胖树网络的路由生成和故障路径诊断过程中。     

基于网络拓扑图的树的代数连通度

代数图谱理论方法在网络设计中发挥重要作用。网络拓扑图的Laplacian矩阵的谱与网络的同步能力有关,代数连通度就是一个刻画同步能力的重要参数。采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论：当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少。进一步地,讨论了树的代数连通度的上界和下界。     

有向赋权网络中任意节点对的最短路径集求解方法

有向赋权网络任意节点对之间的最短路径可能多于一条,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,向其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与前次Floyd算法计算出的最短路径进行比较,筛选出构成最短路径的所有中间节点,并构建路径支撑树,基于路径支撑树确定任意节点对的最短路径集.     

基于PH-Tree多属性索引树的朋友推荐算法

现阶段越来越多的人通过社交网络结识新朋友,如何为用户快速准确推荐朋友是考量平台服务能力的重要指标.提出了一种基于索引树的在线网络朋友推荐方法,即基于网络结构局部特性的思想将用户间的多属性相交值转换为二进制位码向量表示,利用改进后的PH-Tree将所有的向量构造成排序索引树,通过遍历索引树容易确定用户的最佳推荐朋友集.实验证明本方法具有较高的效率和准确率.     

模糊参数下多播QoS路由及分解

文章研究网络参数不确定时的多播（multlcast）QoS路由及分解问题,假定网络链路参数是模糊数,给出了最优可信度树（Most Optimal Reliability Tree,MORT）和树最优延迟分解（Tree Delay Optimal Partition。TDOP）的定义,MORT要求寻找一条联结源节点和目标节点集的支撑树使得树的代价小于约束条件的可信度达到最大,TDOP要求给出端到端约束在树上各条链路的分解使得反映所有链路满足QoS需求的分解函数达到最优．文中给出MORT的近似算法并对误差进行分析,证明TDOP可以在多项式时间内实现并给出具体算法。     

大数据环境下精准客户定位的社交网络分析

大数据为企业进行精准营销提供了重要支撑,精准营销能提升营销效果,提高客户满意度,精准营销的前提是客户识别与选择。通过分析网络个体与群体特征,社交网络分析能够定位核心价值客户。首先对社交网络的中心性进行分析,探讨社交网络节点地位与营销效果的关系,运用社群识别方法,对社交网络进行分群,提出并用MapReduce实现了针对大规模社交网络的社群划分RMCL方法。在此基础上,构建了客户影响度与客户影响因子等指标,并结合中心度指标,定位社群的核心节点,并采用分类回归树方法,研究了社交网络结构与客户消费响应关系,并确定了变量重要性,为企业采取客户差异化营销组合策略提供指导。     

IPv6网络攻击事件溯源中的攻击树节点特征定位

在网络普及的现代,各类网络协议层出不穷,而在当下最为普遍的便是IPv6网络协议,其虽然优化解决了前网络协议中存在的部分问题,但是依旧存在各类安全隐患,为了能更好地预防并构建网络防御系统,需要对过往攻击事件中的攻击树节点特征实施提取。为此,提出了IPv6网络攻击事件溯源中的攻击树节点特征定位。该方法首先利用攻击类型实施扩展,得到攻击树模型,并以此展开计算,之后结合深度学习网络对攻击树的节点特征实施提取,最后利用DV-Hop方法对提取到的攻击树节点特征实施定位。所提方法在定位过程中不仅能耗低,而且误差小,不易受环境干扰,定位稳定性较好,定位效率较高,可以更有效地为改进网络防御系统提供数据支持。     

The number of spanning trees of the regular networks

The classic theorem on graphs and matrices is the Matrix-Tree Theorem, which gives the number of spanning trees t(G) of any graph G as the value of a certain determinant. However, in this paper, we will derive a simple formula for the number of spanning trees of the regular networks.     

The number of spanning trees in a new lexicographic product of graphs

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

Stability analysis of constrained MPC with CLF applied to discrete-time nonlinear system

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

Maximizing the number of spanning trees on the (p,p+2) graphs

This paper considers the problem of maximizing the number of spanning trees. A newly established result is the formula and the graph topology for the maximum number of spanning trees among the class of (p, p+2) graph.     

基于通信网抗毁性的链路重要性比较

为了比较通信链路在通信网抗毁性中的重要性,提出了一种基于链路收缩的算法。该算法通过比较每条链路收缩后的通信网生成树数目,判断每条链路对通信网抗毁性影响的重要程度,生成树数目越多,表明该链路越重要,对通信网抗毁性的影响越大。实验结果表明,该算法计算简单,可以精确地反映不同链路对通信网抗毁性的重要程度。     

On the number of spanning trees of circulant graphs

In this paper, we derive a simple formula for the number of spanning trees of the circulant graphs. Some special cases of the circulant graphs are also taken into account.     

Reliability analysis on the multiple-loop network

The loop network has been one of the popular network topologies used in the design and implementation of local area networks and other configurations. However, the single loop network tends to be unreliable when the number of points in the network becomes large. Reliability can be improved by using the multiple-loop network which is the generalization of the ring network. In this paper the multiple-loop network is first defined based on the construction of the Cayley graph. Then the connectivity properties of this network are discussed. The paper also includes the derivation of a simple formula for the number of spanning trees of the multiple-loop network. As a result, the reliability for high line failure rate can be readily obtained. Finally, we measure Bλ as the number of line disconnecting sets of order λ where λ is the line connectivity. By using this result we can obtain the reliability for small line failure rate.     

Reducing the Height of Independent Spanning Trees in Chordal Rings

This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex v neq r, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. [CHECK END OF SENTENCE] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided.     

The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.