Drawing Weighted Directed Graph from It's Adjacency Matrix

This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory.

A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs

The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.

Parametric Transformation of Timed Weighted Marked Graphs:Applications in Optimal Resource Allocation

Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights)on edges,the performance analysis and resource optimization of such graphs represent a challenging problem.In this paper,we develop an approach to transform a timed weighted marked graph whose initial marking is not given,into an equivalent parametric timed marked graph where the edges have unitary weights.In order to explore an optimal resource allocation policy for a system,an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net.Finally,we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach.Simulation analysis shows that the developed approach is superior to the heuristic approach.

基于Graph-LSTMs的双重位置感知方面级情感分类

目前针对用户评论中方面词项情感分类任务的研究大多忽略了依存句法信息,或并未建立依存句法结构与单词之间的联系。为此,提出一种基于Graph-LSTMs的双重位置感知方面级情感分类方法。通过Graph-LSTMs学习词项的上下文语境特征;在双向GRU的输入中拼接具有双重位置信息的位置向量,优化句子情感编码;利用注意力机制捕获关键的情感特征,实现分类。在SemEval2014的两个数据集上的实验结果表明,该模型相比几种基线模型在准确率和Macro-F1这两个指标上提升明显。

w-DENSITY AND w-BALANCED PROPERTY OF WEIGHTED GRAPHS

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it.In this paper,a good characterization of w-balanced weighted graphs is given.Applying this characterization,many large w-balanced weighted graphs are formed by combining smaller ones.In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed.It is shown that the w-density theory is closely related to the study of SEW(G,w) games.

Improved frequency standard via weighted graph states

We study the spin squeezing property of weighted graph states,which can be used to improve sensitivity in interferometry.We study the time evolution of spin squeezing under local decoherence acting independently on each qubit.Based on the analysis,the spin squeezing of the weighted graph states is somehow robust in the presence of decoherence and the decoherence limit in the improvement of the interferometric sensitivity is still achievable.Furthermore,one can obtain the optimal improvement of sensitivity by tuning the weighted of each edges of the weighted graph state.

A Dirac Type Condition for Heavy Cycles in Weighted Graphs

In this paper we give a Dirac type condition for heavy cycles in a 3-connected weighted graph, reading that if d^w（v）≥ d for all v ∈ V（G）／{x} and w（uz） = w（vz）, when uz, vz ∈ E（G） and uv ∈/ E（G）. Then G contains either an （x, y）-cycle of weight at least 2d or a Hamilton cycle.

Several Classes of Two-weight or Three-weight Linear Codes and Their Applications

Recently,linear codes with a few weights have been extensively studied due to their applications in secret sharing schemes,constant composition codes,strongly regular graphs and so on.In this paper,based on the Weil sums,several classes of two-weight or three-weight linear codes are presented by choosing a proper defining set,and their weight enumerators and complete weight enumerators are determined.Furthermore,these codes are proven to be minimal.By puncturing these linear codes,two classes of two-weight projective codes are obtained,and the parameters of the corresponding strongly regular graph are given.This paper generalizes the results of[7].

A Note on SK, SK₁, SK₂Indices of Interval Weighted Graphs

In this study, the SK, SK1 and SK2 indices are defined on weighted graphs. Then, the SK, SK1 and SK2 indices are defined on interval weighted graphs. Their behaviors are investigated under some graph operations by using these definitions.

Automatic generation of min-weighted persistent formations

This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating rain-weighted rigid and min- weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.

New Formulas for the Mayer and Ree-Hoover Weights of Infinite Families of Graphs

The virial expansion, in statistical mechanics, makes use of the sums of the Mayer weight of all 2-connected graphs on n vertices. We study the Second Mayer weight ωM(c) and the Ree-Hoover weight ωRH(c) of a 2-connected graph c which arise from the hard-core continuum gas in one dimension. These weights are computed using signed volumes of convex polytopes naturally associated with the graph c. In the present work, we use the method of graph homomorphisms, to give new formulas of Mayer and Ree-Hoover weights for special infinite families of 2-connected graphs.

Other Formulas for the Ree-Hoover and Mayer Weights of Families of 2-Connected Graphs

We study graph weights which naturally occur in Mayer’s theory and Ree-Hoover’s theory for the virial expansion in the context of an imperfect gas. We pay particular attention to the Mayer weight and Ree-Hoover weight of a 2-connected graph in the case of the hard-core continuum gas in one dimension. These weights are calculated from signed volumes of convex polytopes associated with the graph. In the present paper, we use the method of graph homomorphisms, to develop other explicit formulas of Mayer weights and Ree-Hoover weights for infinite families of 2-connected graphs.

The Best Constant of Discrete Sobolev Inequality on a Weighted Truncated Tetrahedron

The best constant of discrete Sobolev inequality on the truncated tetrahedron with a weight which describes 2 kinds of spring constants or bond distances. Main results coincides with the ones of known results by Kametaka et al. under the assumption of uniformity of the spring constants. Since the buckyball fullerene C60 has 2 kinds of edges, destruction of uniformity makes us proceed the application to the chemistry of fullerenes.

Design and application of weight gain graphs based on Bandura’s self-efficacy theory for patients on maintenance haemodialysis

Purpose:To design interdialytic and daily weight gain graphs for patients on maintenance haemodialysis and to evaluate their effect on patient adherence to restricted fluid intake.Methods:Forty-five patients on maintenance haemodialysis were recruited from August to October 2012.The graphs were applied for 12 weeks based on Bandura’s self-efficacy theory.Adherence to restricted fluid intake,dialysis adequacy,and satisfaction were compared before and after the graphs were applied.Results:Adherence to restricted fluid intake increased from 53.3%to 91.1%;the mean rate of urea clearance(Kt/V)decreased from 1.197 to 1.311,and the qualified rate increased from 42.5%to 70%.The rate of adherence was 86.77%;acceptance and satisfaction rates were 100%.Conclusion:It is acceptable to apply the graphs clinically for subsequent effective improvement of adherence to restricted fluid intake,promoting dialysis adequacy,and increasing patient satisfaction.Therefore,clinical application of the graphs is worthwhile.

Introducing Weighted Nodes to Evaluate the Cloud Computing Topology

Typical data centers house several powerful ICT (Information and Communication Technology) equipment such as servers, storage devices and network equipment that are high-energy consuming. The nature of these high-energy consuming equipment is mostly accountable for the very large quantities of emissions which are harmful and unfriendly to the environment. The costs associated with energy consumption in data centers increases as the need for more computational resources increases, so also the appalling effect of CO2 (Carbon IV Oxide) emissions on the environment from the constituent ICT facilities-Servers, Cooling systems, Telecommunication systems, Printers, Local Area Network etc. Energy related costs would traditionally account for about 42% (forty-two per cent) of the total costs of running a typical data center. There is a need to have a good balance between optimization of energy budgets in any data center and fulfillment of the Service Level Agreements (SLAs), as this ensures continuity/profitability of business and customer’s satisfaction. A greener computing from what used to be would not only save/sustain the environment but would also optimize energy and by implication saves costs. This paper addresses the challenges of sustainable (or green computing) in the cloud and proffer appropriate, plausible and possible solutions. The idle and uptime of a node and the traffic on its links (edges) has been a concern for the cloud operators because as the strength and weights of the links to the nodes (data centres) increases more energy are also being consumed by and large. It is hereby proposed that the knowledge of centrality can achieve the aim of energy sustainability and efficiency therefore enabling efficient allocation of energy resources to the right path. Mixed-Mean centrality as a new measure of the importance of a node in a graph is introduced, based on the generalized degree centrality. The mixed-mean centrality reflects not only the strengths (weights) and numbers of edges for degree centrality but it combines these features by also applying the closeness centrality measures while it goes further to include the weights of the nodes in the consideration for centrality measures. We illustrate the benefits of this new measure by applying it to cloud computing, which is typically a complex system. Network structure analysis is important in characterizing such complex systems.

A Note on the Spectral Radius of Weighted Signless Laplacian Matrix

A weighted graph is a graph that has a numeric label associated with each edge, called the weight of edge. In many applications, the edge weights are usually represented by nonnegative integers or square matrices. The weighted signless Laplacian matrix of a weighted graph is defined as the sum of adjacency matrix and degree matrix of same weighted graph. In this paper, a brief overview of the notation and concepts of weighted graphs that will be used throughout this study is given. In Section 2, the weighted signless Laplacian matrix of simple connected weighted graphs is considered, some upper bounds for the spectral radius of the weighted signless Laplacian matrix are obtained and some results on weighted and unweighted graphs are found.

自适应相似图联合优化的多视图聚类

相比于单一视图学习,多视图学习往往可以获得学习对象更全面的信息,因而在无监督学习领域,多视图聚类受到了研究者的极大关注,其中基于图的多视图聚类,近年来取得了很大的研究进展.基于图的多视图聚类一般是先从各个视图原始数据学习相似图,再进行视图间相似图的融合来获得最终聚类结果,因此,多视图聚类的效果是由相似图质量和相似图融合方法共同决定的.然而,现有基于图的多视图聚类方法几乎都聚焦在视图间相似图的融合方法研究上,而缺乏对相似图本身质量的关注.这些方法大多数都是孤立地从各视图的原始数据中学习相似图,并且在后续图融合过程中保持相似图不变.这样得到的相似图不可避免地包含噪声和冗余信息,进而影响后续的图融合和聚类.而少量考虑相似图质量的研究,要么相似图构造和图融合过程是直接联立迭代的,要么在预定义相似图过程中提前利用秩约束进一步初始化,要么就是利用相似图存在的一些底层结构来获取融合图的.这些方法对相似图本身改进很小,最终聚类性能提升也十分有限.同时现有基于图的多视图聚类流程也缺乏对各视图间一致性和不一致性的综合考虑,这也会严重影响最终的多视图聚类性能.为了避免低质量预定义相似图对聚类结果的不利影响以及综合考虑视图间一致性与不一致性来提升最终聚类效果,本文提出了一种自适应相似图联合优化的多视图聚类方法.首先通过Hadamard积来获得视图间高质量一致性部分信息,再将每个预定义相似图和这部分信息对标,重构各个视图的预设相似图.这个过程强化了各视图间的一致性部分,弱化了不一致性部分.其次设计了相似图重构改进和图融合联合迭代优化框架,实现了相似图的自适应改进,最终达到相似图和聚类结果共同提升的效果.该方法将相似图改进过程与图融合过程联合起来进行自适应迭代优化,并且在迭代优化中不断强化各视图间的一致性,弱化视图间的不一致性.此外,本文的方法也集成了现有多视图聚类方法的一些优点,自加权以及无需额外聚类步骤等.在九个基准数据集上与八个对比方法的实验验证了本文方法的有效性与优越性.

关于赋权非正则图的A_(α)特征值和特征向量

设G_(ω)=(G,ω)是一个赋权图,其邻接矩阵和赋权度对角矩阵分别A(G_(ω))和D(G_(ω))。对于α∈[0,1],G_(ω)的A_(α)-矩阵为A_(α)(G_(ω))=αD(G_(ω))+(1-α)A(G_(ω))。对于连通赋权非正则图G_(ω),给出了其关于A_(α)-特征值的一些界,并得到了A_(α)-谱半径对应的特征向量中最大分量与最小分量比值的下界。

车联网中基于有向无环图区块链的个性化联邦互蒸馏学习方法

联邦学习(FL)作为一种分布式训练方法,在车联网(IoV)中得到了广泛应用。区别于传统机器学习,FL允许智能网联车辆(CAVs)通过共享模型而非原始数据来协同训练全局模型,从而保护CAV隐私和数据安全。为了提升联邦学习模型精度,降低通信开销,该文首先提出一种基于有向无环图(DAG)区块链和CAVs的IoV架构,分别负责全局模型共享和本地模型训练。其次,设计了一种基于DAG区块链的异步联邦互蒸馏学习(DAFML)算法在本地同时训练教师和学生模型,教师模型的专业级网络结构可取得更高精度,学生模型的轻量级网络结构可降低通信开销,并采用互蒸馏学习使教师模型和学生模型从互相转移的软标签中学习知识以更新模型。此外,为了进一步提高模型精度,基于全局训练轮次和模型精度设定个性化权值来调节互蒸馏占比。仿真结果表明,DAFML算法在模型精度和蒸馏比率方面优于其他比较算法。

面向高速行驶车辆的在线任务卸载决策算法

车载边缘计算中的任务卸载决策主要解决任务何时卸载,以及卸载至哪里执行的问题。车辆的高速行驶会造成卸载接入设备频繁变化,卸载通信链路随时可能中断,这要求车辆一旦获得卸载机会,就必须立即做出卸载决策。现有的卸载决策研究专注于如何最大化任务卸载执行增益,未充分考虑卸载决策时效对卸载策略的影响,导致提出的卸载决策方法的时间复杂度和空间复杂度高,无法用于高速行驶车辆的在线任务卸载决策。为解决上述问题,首先综合考虑卸载决策时效和卸载增益因素的影响,建立高速行驶车辆的任务卸载决策模型,并将其转化为类秘书问题。然后,提出了一种基于加权二部图匹配的在线车载任务卸载决策算法OODA,以协助车辆在依次经过多个异构的边缘服务器时,做出实时的任务卸载决策,并最大化整体卸载执行增益。最后,理论分析OODA算法的竞争比,并采用仿真实验验证该算法的可行性和有效性。