Interactive multigraph visualization and exploration with a two-phase strategy

While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？

On K_(1,k)-factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.

{Ck, Pk, Sk} -Decompositions of Balanced Complete Bipartite Multigraphs

Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of Hi, where . Let Ck, Pk and Sk denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph has a -decomposition if and only if k is even, and .

LOWER BOUNDS ON THE MAXIMUM GENUS OF LOOPLESS MULTIGRAPHS

The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.

Extracting multi-objective multigraph features for the shortest path cost prediction:Statistics-based or learning-based?

Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.

Star-factorization of the Complete Bipartite Multigraphs

LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.

面向代码搜索的函数功能多重图嵌入

如何提高异构的自然语言查询输入和高度结构化程序语言源代码的匹配准确度,是代码搜索的一个基本问题.代码特征的准确提取是提高匹配准确度的关键之一.代码语句表达的语义不仅与其本身有关,还与其所处的上下文相关.代码的结构模型为理解代码功能提供了丰富的上下文信息.提出一个基于函数功能多重图嵌入的代码搜索方法.在所提方法中,使用早期融合的策略,将代码语句的数据依赖关系融合到控制流图中,构建函数功能多重图来表示代码.该多重图通过数据依赖关系显式表达控制流图中缺乏的非直接前驱后继节点的依赖关系,增强语句节点的上下文信息.同时,针对多重图的边的异质性,采用关系图卷积网络方法从函数多重图中提取代码的特征.在公开数据集的实验表明,相比现有基于代码文本和结构模型的方法,所提方法的MRR提高5%以上.通过消融实验也表明控制流图较数据依赖图在搜索准确度上贡献较大.

P_(4k-1)-factorization of bipartite multigraphs

LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m + n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m + n)] is an integer.

The spectrum of path factorization of bipartite multigraphs

Let λK m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P v-factorization of λK m,n is a set of edge-disjoint P v-factors of λK m,n which partition the set of edges of λK m,n . When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P v-factorization of λK m,n . When v is an odd number, we have proposed a conjecture. Very recently, we have proved that the conjecture is true when v = 4k ? 1. In this paper we shall show that the conjecture is true when v = 4k + 1, and then the conjecture is true. That is, we will prove that the necessary and sufficient conditions for the existence of a P 4k+1-factorization of λK m,n are (1) 2km ? (2k + 1)n, (2) 2kn ? (2k + 1)m, (3) m + n ≡ 0 (mod 4k + 1), (4) λ(4k + 1)mn/[4k(m + n)] is an integer.

The Degree Distribution of the Random Multigraphs

In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows： let G（n; {pk}） be the probability space of all the labelled loopless multigraphs with vertex set V = {v1, v2, ..., vn }, in which the distribution of tvi,vj, the number of the edges between any two vertices vi and vj is P{tvi,vj =k}=Pk, k=0, 1,2,...and they are independent of each other. Denote by Xd = Xd（G）,Yd = Yd（G）, Zd = Zd（G） and Zcd = Zcd（G） the number of vertices of G with degree d, at least d, at most d and between c and d. In this paper, we discuss the distribution of Xd, Yd, Zd and Zcd in the probability space G（n; （Pk））.

Multigraphic Degree Sequences and Hamiltonian-connected Line Graphs

Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where ve,ve′are two new vertices not in V(G).If e=e′,then G(e,e′),also denoted by G(e),is obtained from G by replacing e=u1v1 with a path u1vev1.A graph G is strongly spanning trailable if for any e,e′∈E(G),G(e,e′)has a spanning(ve,ve′)-trail.The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties.A sequence d=(d1,d2,⋯,dn)is multigraphic if there is a multigraph G with degree sequence d,and such a graph G is called a realization of d.A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph,and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected.In this paper,we prove that a nonincreasing multigraphic sequence d=(d1,d2)⋯,dn)is strongly spanning trailable if and only if either n=1 and d1=0 or n≥2 and dn≥3.Applying this result,we prove that for a nonincreasing multigraphic sequence d=(d1,d2,⋯,dn),if n≥2 and dn≥3,then d is line-hamiltonian-connected.

Pythagorean Neutrosophic Planar Graphs with an Application in Decision-Making

Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.

多图融合约束半非负矩阵分解的动作分割方法

基于聚类的无监督动作分割方法主要利用序列中相邻帧之间的结构相似性来提高动作分割的准确性。这在实现动作片段内部一致划分的同时给不同动作边界的准确分割带来隐患。为此提出了一种基于多图融合约束矩阵分解的动作分割方法。通过融合序列中的结构相似性和度量相似性信息构造多图融合约束项,融入到半非负矩阵分解中获得序列的低维表示,进而获得序列的k近邻图并利用图割的方法实现准确分割。在两类动作序列上的实验表明,所提方法在保持动作内部一致划分的同时能够准确划分动作边界,明显提升了分割准确性,时间效率也明显提升。

Kinematics-aware multigraph attention network with residual learning for heterogeneous trajectory prediction

Trajectory prediction for heterogeneous traffic agents plays a crucial role in ensuring the safety and efficiency of automated driving in highly interactive traffic environments.Numerous studies in this area have focused on physicsbased approaches because they can clearly interpret the dynamic evolution of trajectories.However,physics-based methods often suffer from limited accuracy.Recent learning-based methods have demonstrated better performance,but they cannot be fully trusted due to the insufficient incorporation of physical constraints.To mitigate the limitations of purely physics-based and learning-based approaches,this study proposes a kinematics-aware multigraph attention network(KAMGAT)that incorporates physics models into a deep learning framework to improve the learning process of neural networks.Besides,we propose a residual prediction module to further refine the trajectory predictions and address the limitations arising from simplified assumptions in kinematic models.We evaluate our proposed model through experiments on two challenging trajectory datasets,namely,ApolloScape and NGSIM.Our findings from the experiments demonstrate that our model outperforms various kinematics-agnostic models with respect to prediction accuracy and learning efficiency.

组织结构的立体多核网络模型

对立体多核网络模型进行了新的阐释,将原来的概念模型向操作层次推进了一步,该模型是将组织作为一个由相互作用的元素构成的、动态的复杂系统来考虑的,它高度概括了组织结构的包括关系多样性、要素多样性、动态特性和层次交错性等方面在内的复杂性和网络中节点的异质性和差异性,是为研究复杂组织而进行仿真设计的前期建模工作.从要素的多样性和关系的多样性出发,初步勾画出立体多核网络的图论描述框架,对以后的仿真设计和计算机编程提出了粗略的设想.最后用一个学术群体的网络研究案例对立体多核网络模型在组织行为宏观处理方面的优点进行了示例性的说明.

多导睡眠图特征提取研究

多导睡眠图是睡眠过程监护和睡眠生理研究的重要工具。本文在6例整夜睡眠监护实验的基础上提出了利用脑电复杂性及多导睡眠图功率谱特征的方法客观反映睡眠的进程,为睡眠的自动分阶分析及睡眠质量的评估研究打下了基础。尤其是脑电复杂性测度与睡眠深度的关系研究对于睡眠生理的研究具有理论意义。

半传递重图的限制性边连通度（英文）

设G=(V,E)是一个重图(包含重边,但不含环).图G的边连通度,记为λ(G),是G的最小边割的基数.我们称G是极大边连通的如果λ(G)=δ(G);称图G是超边连通的如果每个最小边割都是某个点的邻边集合.图G的限制性边连通度,记为λ(G),是图G的最小限制性边割的基数.如果λ(G)达到限制性边连通度的上界,我们称G是λ-最优的.一个二部重图是半传递的如果它作用在每个部分上都是传递的.在本文中,我们将刻画极大边连通的、超边连通的、λ-最优的半传递重图.

基于BP网络的睡眠分阶方法及睡眠质量评估研究

我们利用不同睡眠期脑电复杂性特征与睡眠深度的关系及多道睡眠图功率谱特征,基于3层BP网络进行了睡眠自动分阶的研究,并提出了能部分反映睡眠质量的睡眠时间、浅睡时间、深睡时间、REM时间、觉睡比、醒转次数等参数。通过6例全睡眠监护实验说明,该方法可为睡眠质量的评价提供途径。

粗糙集属性约简的图论方法

通过研究粗糙集与图论的关系,提出了以集合为权的加权多重完全多部图的概念,定义了加权多重完全多部图的邻接矩阵,得到了加权完全多部图与决策表的映射关系;给出了粗糙集决策表信息系统的图论形式和决策表信息系统属性约简的图论方法,并根据图论理论对算法进行了优化;得到了在决策表信息系统中,属性的集合不可以约简的充分必要条件;并进一步提出了基于属性置信度的计算方法和多决策属性的处理方法。编程实验结果证明该方法能有效地降低时间和空间复杂度。