Time varying undirected graphs

Undirected graphs are often used to describe high dimensional distributions. Under sparsity conditions, the graph can be estimated using ? ₁ penalization methods. However, current methods assume that the data are independent and identically distributed. If the distribution, and hence the graph, evolves over time then the data are not longer identically distributed. In this paper we develop a nonparametric method for estimating time varying graphical structure for multivariate Gaussian distributions using an ? ₁ regularization method, and show that, as long as the covariances change smoothly over time, we can estimate the covariance matrix well (in predictive risk) even when p is large.     

Finding reliable subgraphs from large probabilistic graphs

Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by a probabilistic graph G subject to random edge failures, a set of terminal vertices, and an integer K. The objective is to remove K edges from G such that the probability of connecting the terminals in the remaining subgraph is maximized. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.     

Parity games on undirected graphs

We examine the complexity of solving parity games in the special case when the underlying game graph is undirected. For strictly alternating games, that is, when the game graph is bipartite between the players, we observe that the solution can be computed in linear time. In contrast, when the assumption of strict alternation is dropped, we show that the problem is as hard in the undirected case as it is in the general, directed, case.     

Triggering cascades on undirected connected graphs

Consider the following cascading process on an undirected connected graph G(V,E). A set S of vertices, called the seeds, are active initially. Thereafter, an inactive vertex is activated when at least a ρ fraction of its neighbors is active, where ρ∈(0,1]. The cascading process proceeds asynchronously until no more vertices can be activated. This paper proves the existence of at most seeds that can activate all vertices at the end.     

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.     

A layout algorithm for undirected compound graphs

We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions.     

对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

一种连通非加权图的快速聚类方法

图的聚类是数据聚类的一种很重要的变体,一方面通常可以用图来表示数据集中数据的相似度;另一方面对大型复杂网络的分析也引起人们越来越多地关注;而且对图进行聚类分析可以增强图的可视性,有助于可视化的分析、观测和导航。将最大最小方法的基本思想应用于非加权图的聚类,提出一种无向连通非加权图的快速聚类方法,该方法具有简单、聚类时间短、运行效率高、对于大型静态图的聚类具有良好的适应性等特点。     

权长相合的带权无向图画图算法

针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。     

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.     

On m-restricted edge connectivity of undirected generalized De Bruijn graphs

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S.     

Visualizing undirected graphs and symmetric square matrices as overlapping sets

Multimedia Tools and Applications - Undirected graphs and symmetric square matrices are frequently found in various domains. An example is character co-occurrence matrices in digital humanities....     

Finding hidden independent sets in interval graphs

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X?” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.     

Finding strongly connected components in distributed graphs

The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.