A conditional independence algorithm for learning undirected graphical models

When it comes to learning graphical models from data, approaches based on conditional independence tests are among the most popular methods. Since Bayesian networks dominate research in this field, these methods usually refer to directed graphs, and thus have to determine not only the set of edges, but also their direction. At least for a certain kind of possibilistic graphical models, however, undirected graphs are a much more natural basis. Hence, in this area, algorithms for learning undirected graphs are desirable, especially, since first learning a directed graph and then transforming it into an undirected one wastes resources and computation time. In this paper I present a general algorithm for learning undirected graphical models, which is strongly inspired by the well-known Cheng–Bell–Liu algorithm for learning Bayesian networks from data. Its main advantage is that it needs fewer conditional independence tests, while it achieves results of comparable quality.     

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

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

基于Hadoop的电信频繁交往圈算法研究

通过研究电信社交网络的个人交往圈和客户群,结合有向图和无向图,采用邻接链表,挖掘极大团,提出基于Ma-pReduce的频繁交往圈算法F-Graph,不仅找到频繁交往圈和客户群中的核心用户,同时减小了算法复杂度。利于运营商做出更科学的决策,提高市场竞争力。     

Independency relationships and learning algorithms for singly connected networks

Graphical structures such as Bayesian networks or Markov networks are very useful tools for representing irrelevance or independency relationships, and they may be used to efficiently perform reasoning tasks. Singly connected networks are important specific cases where there is no more than one undirected path connecting each pair of variables. The aim of this paper is to investigate the kind of properties that a dependency model must verify in order to be equivalent to a singly connected graph structure, as a way of driving automated discovery and construction of singly connected networks in data. The main results are the characterizations of those dependency models which are isomorphic to singly connected graphs (either via the d-separation criterion for directed acyclic graphs or via the separation criterion for undirected graphs), as well as the development of efficient algorithms for learning singly connected graph representations of dependency models.     

WSM: a novel algorithm for subgraph matching in large weighted graphs

Given an undirected/directed large weighted data graph and a similar smaller weighted pattern graph, the problem of weighted subgraph matching is to find a mapping of the nodes in the pattern graph to a subset of nodes in the data graph such that the sum of edge weight differences is minimum. Biological interaction networks such as protein-protein interaction networks and molecular pathways are often modeled as weighted graphs in order to account for the high false positive rate occurring intrinsically during the detection process of the interactions. Nonetheless, complex biological problems such as disease gene prioritization and conserved phylogenetic tree construction largely depend on the similarity calculation among the networks. Although several existing methods provide efficient methods for graph and subgraph similarity measurement, they produce nonintuitive results due to the underlying unweighted graph model assumption. Moreover, very few algorithms exist for weighted graph matching that are applicable with the restriction that the data and pattern graph sizes are equal. In this paper, we introduce a novel algorithm for weighted subgraph matching which can effectively be applied to directed/undirected weighted subgraph matching. Experimental results demonstrate the superiority and relative scalability of the algorithm over available state of the art methods.     

Wavelength Conversion in All-Optical Networks with Shortest-Path Routing

We consider all-optical networks with shortest-path routing that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We present efficient algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for finding an optimal wavelength assignment when such a placement of converters is known. Our algorithms apply to both undirected and directed networks. Furthermore, we show that the problem of designing such networks, i.e., finding an optimal placement of converters, is MAX SNP-hard in both the undirected and the directed case. Finally, we give a linear-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains NP-hard in bidirected triangle-free planar networks.     

On Optimization and Parallelization of the Little Algorithm for Solving the Travelling Salesman Problem

The paper describes some ways to speed up solution of the NP-complete Traveling Salesman Problem. The classic Little algorithm, belonging to the class of branch-and-bound methods, can solve it both for directed and undirected graphs. For undirected graphs, however, its speed can be increased by eliminating the branches examined earlier from further consideration. We propose changes to be made in the key operations of the algorithm to speed up execution. In addition, we describe the results of an experiment with a significant increase in the speed of solving of the problem by the advanced algorithm. Another way to speed up the solution procedure is to parallelize the algorithm. For problems of this kind, it is difficult to decompose the task into a sufficient number of subtasks that have comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case, the RPM_ParLib library developed by the author is a good approach, enabling the development of high-performance applications for parallel computing on a local network using any.NET-compatible programming language. We selected C# as the programming language. Parallel applications were developed to implement the basic and modified algorithms, as well as to compare them in terms of speed. Experiments were performed for the graphs with up to 45 vertexes and up to 16 network computers. We also investigated the speed increase that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper.     

Multi-level learning based memetic algorithm for community detection

Complex network has become an important way to analyze the massive disordered information of complex systems, and its community structure property is indispensable to discover the potential functionality of these systems. The research on uncovering the community structure of networks has attracted great attentions from various fields in recent years. Many community detection approaches have been proposed based on the modularity optimization. Among them, the algorithms which optimize one initial solution to a better one are easy to get into local optima. Moreover, the algorithms which are susceptible to the optimized order are easy to obtain unstable solutions. In addition, the algorithms which simultaneously optimize a population of solutions have high computational complexity, and thus they are difficult to apply to practical problems. To solve the above problems, in this study, we propose a fast memetic algorithm with multi-level learning strategies for community detection by optimizing modularity. The proposed algorithm adopts genetic algorithm to optimize a population of solutions and uses the proposed multi-level learning strategies to accelerate the optimization process. The multi-level learning strategies are devised based on the potential knowledge of the node, community and partition structures of networks, and they work on the network at nodes, communities and network partitions levels, respectively. Extensive experiments on both benchmarks and real-world networks demonstrate that compared with the state-of-the-art community detection algorithms, the proposed algorithm has effective performance on discovering the community structure of networks.     

An algorithmic study of switch graphs

We derive a variety of results on the algorithmics of switch graphs. On the negative side we prove hardness of the following problems: Given a switch graph, does it possess a bipartite/planar/triangle-free/Eulerian configuration? On the positive side we design fast algorithms for several connectivity problems in undirected switch graphs, and for recognizing acyclic configurations in directed switch graphs.     

Approximating Node Connectivity Problems via Set Covers

Given a graph (directed or undirected) with costs on the edges, and an integer $k$, we consider the problem of finding a $k$-node connected spanning subgraph of minimum cost. For the general instance of the problem (directed or undirected), there is a simple $2k$-approximation algorithm. Better algorithms are known for various ranges of $n,k$. For undirected graphs with metric costs Khuller and Raghavachari gave a $( 2+{2(k-1)}/{n})$-approximation algorithm. We obtain the following results: (i) For arbitrary costs, a $k$-approximation algorithm for undirected graphs and a $(k+1)$-approximation algorithm for directed graphs. (ii) For metric costs, a $(2+({k-1})/{n})$-approximation algorithm for undirected graphs and a $(2+{k}/{n})$-approximation algorithm for directed graphs. For undirected graphs and $k=6,7$, we further improve the approximation ratio from $k$ to $\lceil (k+1)/2 \rceil=4$; previously, $\lceil (k+1)/2 \rceil$-approximation algorithms were known only for $k \leq 5$. We also give a fast $3$-approximation algorithm for $k=4$. The multiroot problem generalizes the min-cost $k$-connected subgraph problem. In the multiroot problem, requirements $k_u$ for every node $u$ are given, and the aim is to find a minimum-cost subgraph that contains $\max\{k_u,k_v\}$ internally disjoint paths between every pair of nodes $u,v$. For the general instance of the problem, the best known algorithm has approximation ratio $2k$, where $k=\max k_u$. For metric costs there is a 3-approximation algorithm. We consider the case of metric costs, and, using our techniques, improve for $k \leq 7$ the approximation guarantee from $3$ to $2+{\lfloor (k-1)/2 \rfloor}/{k} < 2.5$.     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

节点不对称转移概率的网络社区发现算法

社区发现是当前社会网络研究领域的一个热点和难点,现有的研究方法包括：（1）优化以网络拓扑结构为基础的社区质量指标;（2）评估节点间的相似性并进行聚类;（3）根据特定网络设计相应的社区模型等.这些方法存在如下问题：（1）通用性不高,难以同时在无向网络和有向网络上发挥出好的效果;（2）无法充分利用网络的结构信息,在真实数据集上表现不佳.针对上述问题,提出一种基于节点不对称转移概率的网络社区发现算法CDATP.该算法通过分析网络拓扑结构来设计节点转移概率,并使用random walk方法评估节点对网络社区的重要性.最后,以重要性较高的节点作为核心构造网络社区.与现有的基于random walk的方法不同,CDATP为网络中节点设计的转移概率具有不对称性,并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明,CDATP在人工模拟数据集和真实数据集上均比其他最新算法有更好的表现.     

Updating method for the computation of orbits in parallel and sequential dynamical systems

In this article, we provide a matrix method in order to compute orbits of parallel and sequential dynamical systems on Boolean functions. In this sense, we develop algorithms for systems defined over directed (and undirected) graphs when the evolution operator is a general minterm or maxterm and, likewise, when it is constituted by independent local Boolean functions, so providing a new tool for the study of orbits of these dynamical systems.     

Answering exact distance queries on real-world graphs with bounded performance guarantees

The ability to efficiently obtain exact distance information from both directed and undirected graphs is desired by many real-world applications. In this work, we unified the query indexing efforts on directed and undirected graphs into one by proposing the TreeMap approach. Our approach has very tight bounds on query time, index size, and construction time for answering queries on both directed and undirected graphs. The query time complexity is close to constant for graphs with a small width of tree decomposition, and the index construction can be completed without materializing the distance matrix or other high-cost operations. In the empirical study, we demonstrated that the TreeMap approach in general performs much better than competitive methods in indexing real graphs for answering exact distance queries.     

Derandomizing random walks in undirected graphs using locally fair exploration strategies

We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot’s walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First, always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G = (V, E) of diameter D within time O(D|E|), and in the long run traverses all edges of G with the same frequency.     

Bayesian learning of graphical vector autoregressions with unequal lag-lengths

Graphical modelling strategies have been recently discovered as a versatile tool for analyzing multivariate stochastic processes. Vector autoregressive processes can be structurally represented by mixed graphs having both directed and undirected edges between the variables representing process components. To allow for more expressive vector autoregressive structures, we consider models with separate time dynamics for each directed edge and non-decomposable graph topologies for the undirected part of the mixed graph.Contrary to static graphical models, the number of possible mixed graphs is extremely large even for small systems, and consequently, standard Bayesian computation based on Markov chain Monte Carlo is not in practice a feasible alternative for model learning. To obtain a numerically efficient approach we utilize a recent Bayesian information theoretic criterion for model learning, which has attractive properties when the potential model complexity is large relative to the size of the observed data set. The performance of our method is illustrated by analyzing both simulated and real data sets. Our simulation experiments demonstrate the gains in predictive accuracy which can obtained by considering structural learning of vector autoregressive processes instead of unstructured models. The analysis of the real data also shows that the understanding of the dynamics of a multivariate process can be improved significantly by considering more flexible model classes.     

Distance‐based control of formations with hybrid communication topology

In this paper, we focus on the control of multiagent formations with hybrid communication topology through a distance‐based approach. By saying hybrid topology, we mean that the communication topology contains both undirected and directed links, or the underlying graph of the formation contains both undirected and directed edges. A new type of graph, ie, hybrid graph, is introduced. We discuss the persistence of hybrid graphs and present the persistence verification strategy for hybrid graphs. It is proved that all the minimally persistent hybrid graphs can be obtained from persistent directed graphs by the operation of edge transformation. As the main result, it is shown that multiagent formations modeled by acyclic persistent hybrid graphs can be stabilized locally under distance‐based controllers.     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

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

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

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。