Centrality Based Visualization of Small World Graphs

Current graph drawing algorithms enable the creation of two dimensional node‐link diagrams of huge graphs. However, for graphs with low diameter (of which “small world” graphs are a subset) these techniques begin to break down visually even when the graph has only a few hundred nodes. Typical algorithms produce images where nodes clump together in the center of the screen, making it hard to discern structure and follow paths. This paper describes a solution to this problem, which uses a global edge metric to determine a subset of edges that capture the graph's intrinsic clustering structure. This structure is then used to create an embedding of the graph, after which the remaining edges are added back in. We demonstrate applications of this technique to a number of real world examples.     

Combinatorial search versus genetic algorithms: A case study based on the generalized median graph problem

The computation of generalized median graphs (the graph with the smallest average edit distance to all graphs in a given set of graphs) is highly computationally complex. As a matter of fact, it is exponential in the number of nodes of the union of all graphs under consideration. Thus, the generalized median graph computation problem seems to be a suitable and challenging testbed for a comparison of combinatorial search and genetic algorithms. Two solutions are described in this paper. The first is an exact algorithm based on combinatorial search, while the second is a genetic algorithm. Both approaches are compared to each other in a series of experiments.     

基于图神经网络的方面级情感分析

目前基于循环神经网络和注意力机制的方面级情感分析模型缺乏解释相关句法约束和远程单词依赖关系.针对该问题提出结合句子依存树和单词序列信息建立句子关系图模型.首先将句子表示为图,单词作为图的节点,依存句法树的边和单词序列作为图的边;然后提出邻接矩阵标记方案对句子关系图进行标记;最后利用图神经网络实现节点和边的分类任务.该模型在SemEval2014任务中的restaurant和laptop两个数据集上进行实验,在两个数据集上F1值提升了5％左右.实验结果表明,将句子转换成图利用图神经网络对句子进行方面级情感分析是有益的.     

基于局部有限搜索的无向图近似最大团快速求解算法

无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。     

Pathfinder: Visual Analysis of Paths in Graphs

The analysis of paths in graphs is highly relevant in many domains. Typically, path‐related tasks are performed in node‐link layouts. Unfortunately, graph layouts often do not scale to the size of many real world networks. Also, many networks are multivariate, i.e., contain rich attribute sets associated with the nodes and edges. These attributes are often critical in judging paths, but directly visualizing attributes in a graph layout exacerbates the scalability problem. In this paper, we present visual analysis solutions dedicated to path‐related tasks in large and highly multivariate graphs. We show that by focusing on paths, we can address the scalability problem of multivariate graph visualization, equipping analysts with a powerful tool to explore large graphs. We introduce Pathfinder, a technique that provides visual methods to query paths, while considering various constraints. The resulting set of paths is visualized in both a ranked list and as a node‐link diagram. For the paths in the list, we display rich attribute data associated with nodes and edges, and the node‐link diagram provides topological context. The paths can be ranked based on topological properties, such as path length or average node degree, and scores derived from attribute data. Pathfinder is designed to scale to graphs with tens of thousands of nodes and edges by employing strategies such as incremental query results. We demonstrate Pathfinder's fitness for use in scenarios with data from a coauthor network and biological pathways.     

Scheduling with Conflicts on Bipartite and Interval Graphs

In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.     

Diversified top-<Emphasis Type="Italic">k</Emphasis> clique search

Maximal clique enumeration is a fundamental problem in graph theory and has been extensively studied. However, maximal clique enumeration is time-consuming in large graphs and always returns enormous cliques with large overlaps. Motivated by this, in this paper, we study the diversified top-k clique search problem which is to find top-k cliques that can cover most number of nodes in the graph. Diversified top-k clique search can be widely used in a lot of applications including community search, motif discovery, and anomaly detection in large graphs. A naive solution for diversified top-k clique search is to keep all maximal cliques in memory and then find k of them that cover most nodes in the graph by using the approximate greedy max k-cover algorithm. However, such a solution is impractical when the graph is large. In this paper, instead of keeping all maximal cliques in memory, we devise an algorithm to maintain k candidates in the process of maximal clique enumeration. Our algorithm has limited memory footprint and can achieve a guaranteed approximation ratio. We also introduce a novel light-weight \(\mathsf {PNP}\)-\(\mathsf {Index}\), based on which we design an optimal maximal clique maintenance algorithm. We further explore three optimization strategies to avoid enumerating all maximal cliques and thus largely reduce the computational cost. Besides, for the massive input graph, we develop an I/O efficient algorithm to tackle the problem when the input graph cannot fit in main memory. We conduct extensive performance studies on real graphs and synthetic graphs. One of the real graphs contains 1.02 billion edges. The results demonstrate the high efficiency and effectiveness of our approach.     

Estimation and marginalization using the Kikuchi approximation methods

In this letter, we examine a general method of approximation, known as the Kikuchi approximation method, for finding the marginals of a product distribution, as well as the corresponding partition function. The Kikuchi approximation method defines a certain constrained optimization problem, called the Kikuchi problem, and treats its stationary points as approximations to the desired marginals. We show how to associate a graph to any Kikuchi problem and describe a class of local message-passing algorithms along the edges of any such graph, which attempt to find the solutions to the problem. Implementation of these algorithms on graphs with fewer edges requires fewer operations in each iteration. We therefore characterize minimal graphs for a Kikuchi problem, which are those with the minimum number of edges. We show with empirical results that these simpler algorithms often offer significant savings in computational complexity, without suffering a loss in the convergence rate. We give conditions for the convexity of a given Kikuchi problem and the exactness of the approximations in terms of the loops of the minimal graph. More precisely, we show that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically. Together with the fact that in the cycle-free case, the iterative algorithms are equivalent to the well-known belief propagation algorithm, our results imply that, generically, the Kikuchi approximation method can be exact if and only if traditional junction tree methods could also solve the problem exactly.     

An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs

In this paper, a graph problem on connected, weighted, undirected graphs, called the searchlight guarding problem, is considered. Assume that there is a fugitive who moves along the edges of the graph at a random speed. The task involves placing a set of searchlights at vertices to search the edges of the graph and to spot the fugitive. Suppose that placing a searchlight at some vertex incurs some building cost. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total cost of the vertices in S is minimized. If there is more than one set of searchlights, each with a minimum building cost, then identify the set with the minimum search time, that is, where the time slots needed to spot the fugitive is the minimum. As is well established, the problem is NP-hard on weighted bipartite graphs but is linear-time solvable on weighted trees. In this paper, the design of a linear-time optimal algorithm for the searchlight guarding problem on weighted interval graphs is presented. It entails two phases. In the first phase, a set of searchlights with minimum guarding cost is identified and the search directions of all edges are assigned. To achieve this task, a new problem, called the edge-direction assignment problem, is first defined and the problem on weighted complete-split graphs is solved by the greedy strategy. Based on this computational result, the problem of finding the set of searchlights with minimum guarding cost and assigning the search directions of all edges is solved by the dynamic programming strategy. Then, in the second phase, the search time slots of each edge are determined on the basis of the results of the first phase and on some properties of interval graphs.     

Estimating graph distance and centrality on shared nothing architectures

We present a parallel toolkit for pairwise distance computation in massive networks. Computing the exact shortest paths between a large number of vertices is a costly operation, and serial algorithms are not practical for billion‐scale graphs. We first describe an efficient parallel method to solve the single source shortest path problem on commodity hardware with no shared memory. Using it as a building block, we introduce a new parallel algorithm to estimate the shortest paths between arbitrary pairs of vertices. Our method exploits data locality, produces highly accurate results, and allows batch computation of shortest paths with 7% average error in graphs that contain billions of edges. The proposed algorithm is up to two orders of magnitude faster than previously suggested algorithms and does not require large amounts of memory or expensive high‐end servers. We further leverage this method to estimate the closeness and betweenness centrality metrics, which involve systems challenges dealing with indexing, joining, and comparing large datasets efficiently. In one experiment, we mined a real‐world Web graph with 700 million nodes and 12 billion edges to identify the most central vertices and calculated more than 63 billion shortest paths in 6 h on a 20‐node commodity cluster. Copyright © 2014 John Wiley & Sons, Ltd.     

Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.     

A graph-theoretic language extension for an interactive computer graphics environment

A programming language extension, AGILE, for the processing of graphs within an interactive computer graphics environment, is defined. The language is intended to be used for expressing and illustrating graph-theoretic algorithms and applications. However it does not deal with the actual drawing or display of graphs; rather one is able to access an existing general-purpose graphics package. The language then is intended to be used, in conjunction with a graphics package, as a tool for the production of more specialised graphics systems: the language allows one to naturally exploit the underlying graph structure found in a wide class of problems, while a graphics environment permits the elegant display of (and interaction with) such representations.AGILE extends the host language, C, by the addition of a graph database, and operators and control structures to manipulate this database. The graph structure is composed of five basic types: nodes, edges, graphs, sets and bugs (references). A general set of operators and tests are provided, including those for entity creation and deletion, node and edge traversal and tests for equality and containment of sets and graphs. Edges may be treated as being either directed or undirected; also multiple edges between nodes and self-loops are allowed. Arbitrary values and properties may be associated with each of the basic types. In particular, since a node may have a graph as value, a graph hierarchy is possible. Graphics primitives are provided by the GPAC graphics system.Three substantial applications have been programmed in the language: a system for producing diagrams of graphs and a class of data structures, a system for animating four algorithms for finding the maximum flow in a network, and a system for animating and making films of systems dynamics models.Several examples of programmes written in AGILE are included.     

面向超图数据的最大独立集算法

超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出4种高效的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在10个真实超图数据集上进行实验, 结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

基于贪婪策略的紧密k核子图查询

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询（CRKSQ）问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。     

ImPrEd: An Improved Force‐Directed Algorithm that Prevents Nodes from Crossing Edges

PrEd [ [Ber00] ] is a force‐directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler‐like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly‐restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEdproves to be consistently faster than PrEd.     

A Genetic Algorithm for Finding the Pagenumber of Interconnection Networks

A “book-embedding” of a graph G comprises embedding the graph's nodes along the spine of a book and embedding the edges on the pages so that the edges embedded on the same page do not intersect. This is also referred to as the page model. The “pagenumber” of a graph is the thickness of the smallest (in number of pages) book into which G can be embedded. The problem has been studied only for some specific kind of graphs. The pagenumber problem is known to be NP-complete, even if the order of nodes on the spine is fixed. Using genetic algorithms, we describe the first algorithm for solving the pagenumber problem that can be applied on arbitrary graphs. Experimental results for several kinds of graphs are obtained. We were particularly interested in graphs that correspond to some well-known interconnection networks (such as hypercubes and meshes). We also introduced and experimented with 2-D pagenumber model for embedding graphs.     

An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs

In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal. Received: 12 March 1996 / 27 May 1997     

Deadlock-free adaptive routing in multicomputer networks usingvirtual channels

The use of adaptive routing in a multicomputer interconnection network improves network performance by using all available paths and provides fault tolerance by allowing messages to be routed around failed channels and nodes. Two deadlock-free adaptive routing algorithms are described. Both algorithms allocate virtual channels using a count of the number of dimension reversals a packet has performed to eliminate cycles in resource dependency graphs. The static algorithm eliminates cycles in the network channel dependency graph. The dynamic algorithm improves virtual channel utilization by permitting dependency cycles and instead eliminating cycles in the packet wait-for graph. It is proved that these algorithms are deadlock-free. Experimental measurements of their performance are presented     

Fast online graph clustering via Erd?s-Rényi mixture

In the context of graph clustering, we consider the problem of simultaneously estimating both the partition of the graph nodes and the parameters of an underlying mixture of affiliation networks. In numerous applications the rapid increase of data size over time makes classical clustering algorithms too slow because of the high computational cost. In such situations online clustering algorithms are an efficient alternative to classical batch algorithms. We present an original online algorithm for graph clustering based on a Erd?s-Rényi graph mixture. The relevance of the algorithm is illustrated, using both simulated and real data sets. The real data set is a network extracted from the French political blogosphere and presents an interesting community organization.