图的表示与可视化方法综述

图是由节点和边组成的图形,通常用于表示两个或多个实体之间的关系。基于图的分析可以帮助人们理解实体关系的结构和本质,探索图中的隐含关联。图的表示与可视化方法在图分析中起着的重要作用,在图可视化研究中首先要考虑知识传达是否准确、人们的思维地图等方面,同时还要考虑图形是否美观、构建图所需的时间、以及计算机的性能等问题。综述了基于节点-链接、邻接矩阵以及图嵌入的图表示方法、图布局算法以及可视化方法,并对这些方法进行归纳与对比。最后对图表示与可视化技术的未来发展趋势进行了展望。     

结构VAR模型辨识的条件互信息图模型

在结构向量自回归(VAR)模型辨识的图模型中引入信息论方法.定义了线性条件互信息图,图中的结点表示时间序列不同时刻的随机变量,结点间的边表示随机变量之间存在的因果相依关系.提出了随机变量之间条件线性联系存在性的信息论检验方法.图中边的存在性用基于线性条件互信息的枢轴量检验,枢轴量的显著性用置换检验决定.用统计分析的方法确定当前变量之间联系的方向,建立了有向非循环图.最后以模拟序列为例,验证了所提出的方法是可行且有效的.     

PACKING A TREE OF ORDER p WITH A （p,p＋1）—GRAPH

Let G1 and G2 be two graphs of the same order,If G1 is isomorphic to a spanning subgraph of the complement of G2,then we say that G1 and G2 are packable.A graph G is called a (p,m)-graph if G has p vertices and m edges.The main purpose of this paper is to present a necessary and sufficient condition for a tree of order p and a (p,p 1)-graph to be packable.     

用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。     

On the Tractability of Shortest Path Problems in Weighted Edge-Coloured Graphs

A weighted edge-coloured graph is a graph for which each edge is assigned both a positive weight and a discrete colour, and can be used to model transportation and computer networks in which there are multiple transportation modes. In such a graph paths are compared by their total weight in each colour, resulting in a Pareto set of minimal paths from one vertex to another. This paper will give a tight upper bound on the cardinality of a minimal set of paths for any weighted edge-coloured graph. Additionally, a bound is presented on the expected number of minimal paths in weighted edge–bicoloured graphs. These bounds indicate that despite weighted edge-coloured graphs are theoretically intractable, amenability to computation is typically found in practice.     

Learning Granger causality graphs for multivariate nonlinear time series

An information theory method is proposed to test the. Granger causality and contemporaneous conditional independence in Granger causality graph models. In the graphs, the vertex set denotes the component series of the multivariate time series, and the directed edges denote causal dependence, while the undirected edges reflect the instantaneous dependence. The presence of the edges is measured by a statistics based on conditional mutual information and tested by a permutation procedure. Furthermore, for the existed relations, a statistics based on the difference between general conditional mutual information and linear conditional mutual information is proposed to test the nonlinearity. The significance of the nonlinear test statistics is determined by a bootstrap method based on surrogate data. We investigate the finite sample behavior of the procedure through simulation time series with different dependence structures, including linear and nonlinear relations.     

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.     

双目标进化算法求解图着色问题

根据图着色问题的特征,提出了求解图着色问题的双目标模型;设计的有效、简洁的杂交算子和变异算子,均直接产生可行的后代个体;理论分析表明算法以概率1收敛到问题的最优解集.对标准算例进行了仿真实验,结果表明,双目标进化算法可以获得问题高质量的解,即对图进行着色所使用的颜色接近图的色数.     

Bayesian empirical likelihood estimation of quantile structural equation models

Structural equation model (SEM) is a multivariate analysis tool that has been widely applied to many fields such as biomedical and social sciences. In the traditional SEM, it is often assumed that random errors and explanatory latent variables follow the normal distribution, and the effect of explanatory latent variables on outcomes can be formulated by a mean regression-type structural equation. But this SEM may be inappropriate in some cases where random errors or latent variables are highly nonnormal. The authors develop a new SEM, called as quantile SEM (QSEM), by allowing for a quantile regression-type structural equation and without distribution assumption of random errors and latent variables. A Bayesian empirical likelihood (BEL) method is developed to simultaneously estimate parameters and latent variables based on the estimating equation method. A hybrid algorithm combining the Gibbs sampler and Metropolis-Hastings algorithm is presented to sample observations required for statistical inference. Latent variables are imputed by the estimated density function and the linear interpolation method. A simulation study and an example are presented to investigate the performance of the proposed methodologies.     

多色图及其在仿真复杂对象及系统时的应用

在介绍了多色图的概念,多色图的组成和多色图的数学模型后,阐述了在围道析取矩阵的多色图PG和围道合取矩阵的多色图PG中路径F（μi）的计算公式和方法。最后举出了简例。多色图这一新的信息处理工具对复杂对象和系统具有强大的仿真功能。     

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...     

一种图形数据的存储和查询方案

提出了一种以图形、图段和图元为基本元素,通过无环有向图结构建立图形数据的存储模式,在关系型数据库上以嵌套关系存储图形数据的方法,讨论了该存储模式下图形数据查询的语言和算法,解决了图形存储必须依赖于大型工程数据库系统的问题,同时给出了一个模型系统Ｔｒｉｅｂａｓｅ的例子。     

多模态公文的结构知识抽取与组织研究

针对目前基于三元组知识构建的知识图谱结构逻辑性弱、难以形成知识体系的问题, 以公文应用背景为牵引, 提出多模态知识结构要素抽取模型, 构建多模态公文文档数据集GovDoc-CN, 在文本和图像两个模态对文档中包括各级标题、摘要、作者、成文时间、文档编号等在内的知识结构要素进行抽取。设计文档结构树模型对抽取的文档知识结构要素进行组织, 并构建结构化图网络实现文档的组织和管理。实验证明, 相较于单一模态的抽取模型, 多模态知识结构要素抽取模型取得了明显的效果提升, 文档结构树模型和基于文档结构树模型构建的结构化图网络为文档知识的组织与管理提供了一种新途径, 具有重要的应用价值。     

影响交通信息支付意愿的关键因素实证研究

以GPS应用为代表的信息服务收费开始受到关注,文中就该问题从交通行为科学的角度进行了探讨,首先就问题解决的前提条件设计了个体特征、信息价值,信息采纳和支付意愿4个隐变量,并根据文献研究和实践经验,分别给出了描述这4个隐变量的可量化的19项显示指标,由此利用结构方程建模技术,建立了反映这些隐变量和显示指标间关系的模型,然后通过问卷调查所收集到的数据,使用LISREL软件进行了分析和计算,并根据计算结果的拟合度,确认了结构方程模型的适用性.研究结果表明,信息价值与信息采纳之间的影响关系最弱,而个体特征对其余3个变量的影响都非常显著.     

基于蚁群算法的复杂系统脆性研究

针对复杂系统的研究,提出了一种复杂系统脆性分析的方法。建立了复杂系统脆性的赋权图模型,以图的边描述子系统之间的脆性联系,边的权值描述子系统之间的脆性联系程度。而且定义了系统最大崩溃路径,并且提出了一种求解系统最大崩溃路径的蚁群算法。为了进一步说明问题,又以24-Bus IEEE测试系统为例验证了新算法,并对算法中参数的选取进行了讨论。     

反映式与构成式测量模型的差异：基于TAM的实证研究

测量模型的选择是实证研究过程中的重要环节，区分反映式测量模型和构成式测量模型是正确构建管理理论的基础.在分析反映式和构成式两种测量模型差异的基础上，以技术采纳模型为例，通过对7次共1951份实际调查数据的分析，利用偏最小二乘法的结构方程模型，实证比较了两种测量模型在不同的样本规模、不同的研究情境和不同调查时间下外部效度和对内生潜变量解释能力上的差异.研究结果表明反映式测量模型具有稳定的外部效度，构成式测量模型的外部效度受到样本规模、研究情境和调查时间的影响；在因变量解释能力方面，构成式测量模型比反映式测量模型强的假设没有得到支持，即使当构成式测量模型误设为反映式测量模型时，其因变量解释能力也不一定显著增强.     

Discovery of latent structures: Experience with the CoIL Challenge 2000 data set*

The authors present a case study to demonstrate the possibility of discovering complex and interesting latent structures using hierarchical latent class （HLC） models. A similar effort was made earlier by Zhang （2002）, but that study involved only small applications with 4 or 5 observed variables and no more than 2 latent variables due to the lack of efficient learning algorithms. Significant progress has been made since then on algorithmic research, and it is now possible to learn HLC models with dozens of observed variables. This allows us to demonstrate the benefits of HLC models more convincingly than before. The authors have successfully analyzed the CoIL Challenge 2000 data set using HLC models. The model obtained consists of 22 latent variables, and its structure is intuitively appealing. It is exciting to know that such a large and meaningful latent structure can be automatically inferred from data.     

模拟大脑皮层结构和功能连接的神经网络研究

为了模拟动物大脑皮层结构连接与功能连接间的关系，为机器学习提供新的思路，本文用图论测度表示网络的结构，用信息论测度表示功能整合和功能分离间的相互作用，采用图选择的方法对随机图进行变异和选择，确定与特定的功能动力学模式相对应的网络结构，并研究在外界刺激信号作用下，系统连接与感觉层间的匹配关系。仿真结果表明：由图选择获得的网络结构，呈现若干密集的顶点区，区域间松散连接，具有功能分离与功能整合的特点。在外界信号刺激下，特定的结构模式可以使系统与感觉层信号的统计结构间达到最大程度的匹配。     

速度拖引干扰下运动目标检测

给出了速度拖引干扰下,雷达接收信号模型,提出了一种运动目标的检测方法。利用Morlet小波变换的性质,通过对雷达接收信号进行时-频分析,干扰信号参数估计,相位补偿,滤波,再进行时-频分析,得到目标回波信号的三维时频图及其等高线图,由此进行目标检测。模拟结果表明,此方法是可行的。     

Forbidden Subgraphs, Distance,and Hamiltonicity

ＦｏｒｂｉｄｄｅｎＳｕｂｇｒａｐｈｓ，Ｄｉｓｔａｎｃｅ，ａｎｄＨａｍｉｌｔｏｎｉｃｉｔｙＨＵＺｈｉｑｕａｎＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＨｕａｚｈｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７０Ａｂｓｔｒａｃｔ：Ａｇｒ...