Search

This paper presents the first distributed triangle listing algorithm with provable CPU, I/O, Memory, and Network bounds. Finding all triangles (3-cliques) in a graph has numerous applications for density and connectivity metrics. The majority of existing algorithms for massive graphs are sequential processing and distributed versions of algorithms do not guarantee their CPU, I/O, Memory or Network requirements. Our Parallel and Distributed Triangle Listing (PDTL) framework focuses on efficient external-memory access in distributed environments instead of fitting subgraphs into memory. It works by performing efficient orientation and load-balancing steps, and replicating graphs across machines by using an extended version of Hu et al.'s Massive Graph Triangulation algorithm. As a result, PDTL suits a variety of computational environments, from single-core machines to high-end clusters. PDTL computes the exact triangle count on graphs of over 6 billion edges and 1 billion vertices (e.g. Yahoo graphs), outperforming and using fewer resources than the state-of-the-art systems PowerGraph, OPT, and PATRIC by 2 times to 4 times. Our approach highlights the importance of I/O considerations in a distributed environment, which has received less attention in the graph processing literature.

A fundamental problem in network reliability analysis is to find the connectedness probability of a random graph, subject to perfect nodes and link failures. If, in addition, we consider independent link failures with identical probability ρ, the connectedness probability is known as the all-terminal reliability. It is well-known that the all-terminal reliability is a polynomial in the variable ρ ∊ [0,1], and its determination belongs to the class of NP-Hard problems. In this paper we address the following network design problem: given a fixed number of nodes and links p and q, find the graph that maximizes the reliability polynomial uniformly on the compact set ρ ∊ [0,1] for all (p, q)-graphs whenever it exists. These graphs are called uniformly most-reliable graphs. There exists easy graphs, where the reliability polynomial is obtained in a straightforward manner. The interplay between easy graphs and uniformly most-reliable graphs is first studied. Then, Wagner graph is discovered as a uniformly most-reliable graph, inspired by greedy augmentations of a cycle. The paper is closed with a conjecture on the existence of (n, n + 4) uniformly most-reliable graphs.

Much attention has been paid to the diagonal flips in maximal planar graphs. In this paper, we firstly focus on the properties of the unflippable edges in maximal planar graphs, and propose the concept of K4-embedding. Also, we prove that for a maximal planar graph G with order n(⋝ 5), an edge e ∊ E(G) is unflippable if and only if e is either incident to a 3-degree vertex or a supporting edge of a K4-embedding. Secondly, we give the necessary and sufficient condition for a maximal planar graph G has a given number of flippable edges. Finally, we show a general algorithm of the enumeration of flippable edges in maximal planar graphs by the extending-contracting operational system, with the time complexity of O(n2).

Evaluating an extremely useful graph property, the spectral radius (largest absolute eigenvalue of the graph adjacency matrix), for large graphs requires excessive computing resources. This problem becomes especially challenging, for instance with distributed or remote storage, when accessing the whole graph itself is expensive in terms of memory or bandwidth. One approach to tackle this challenge is to estimate the spectral radius of the graph while reading only a small portion of the graph. In this paper we present a sampling approach to estimate the spectral radius of large graphs. We define a score for vertices that i) is more of a combinatorial nature and is easier to compute and ii) has solid theoretical justifications hence, it closely approximate a vertex's contribution to the largest eigenvalue of the graph. Using this score, we model the sampling problem as a budgeted optimization problem and design a greedy algorithm to select a subgraph whose spectral radius approaches that of the whole graph. We provide analytical bound on computational complexity of our algorithm. We demonstrate effectiveness of our algorithm on various synthetic and real-world graphs and show that our algorithm also empirically outperforms known techniques. Furthermore, we compare the quality of our results to estimates obtained from well known upper and lower bounds known in the spectral graph theory literature.

Observations about two-covers and two-partitions of graphs lead to a new heuristic to find good two-covers of graphs.

This article describes an alternative representation of graphs, using symmetries. We define the class of graphs that are compressed using this representation as symmetry-compressible graphs. This class of graphs is extended into the class of near symmetry-compressible graphs, which includes many more graphs arising in practical applications. To demonstrate the practical potential of the proposed concepts, an empirical evaluation of two algorithms is given.

Finding of frequent sub-graphs is an important operation on graphs and it is defined as detection of all sub-graphs that appear frequently in a set of graphs. This paper proposes detection of frequent sub-community graph from n-set of community graph of villages; are useful for characterizing community graph sets, finding difference among groups of community graphs, classifying and clustering of community graphs, and building community graph indices leading to knowledge extraction. The given n-community graphs of villages and the sub-community graph, which is to be detected are first represented as adjacency matrices. Then the sub-community graph adjacency matrix is compared with the n-community graph's adjacency matrices sequentially. The paper concludes with analysis of the proposed algorithm using graph mining techniques with supportive example, satisfactory results and screenshots.

For any positive integer k, the total k-domatic partition problem is to partition the vertices of a graph G into k pairwise disjoint total dominating sets. In this paper, we study the problem for planar graphs, chordal bipartite graphs, convex bipartite graphs, and bipartite permutation graphs. We show that the total 3-domatic partition problem on planar graphs is NP-complete. Moreover, we give an alternative algorithm to solve the total k-domatic partition problem for chordal bipartite graphs with weak elimination orderings, and adapt it to solve the problem in linear time for bipartite permutation graphs and convex bipartite graphs even if Gamma-free forms of the adjacency matrices of the considered graphs are not given.

How do the k-core structures of real-world graphs look like? What are the common patterns and the anomalies? How can we use them for algorithm design and applications? A k-core is the maximal subgraph where all vertices have degree at least k. This concept has been applied to such diverse areas as hierarchical structure analysis, graph visualization, and graph clustering. Here, we explore pervasive patterns that are related to k-cores and emerging in graphs from several diverse domains. Our discoveries are as follows: (1) Mirror Pattern: coreness of vertices (i.e., maximum k such that each vertex belongs to the k-core) is strongly correlated to their degree. (2) Core-Triangle Pattern: degeneracy of a graph (i.e., maximum k such that the k-core exists in the graph) obeys a 3-to-1 power law with respect to the count of triangles. (3) Structured Core Pattern: degeneracy-cores are not cliques but have non-trivial structures such as core-periphery and communities. Our algorithmic contributions show the usefulness of these patterns. (1) Core-A, which measures the deviation from Mirror Pattern, successfully finds anomalies in real-world graphs complementing densest-subgraph based anomaly detection methods. (2) Core-D, a single-pass streaming algorithm based on Core-Triangle Pattern, accurately estimates the degeneracy of billion-scale graphs up to 7× faster than a recent multipass algorithm.(3) Core-S, inspired by Structured Core Pattern, identifies influential spreaders up to 17× faster than top competitors with comparable accuracy.

Clustering vertices in graphs or in sequences of graphs has important applications in network science, bioinformatics, and other areas. Most research to date has focused on static graphs or sequences where the number of vertices does not change. We propose a new algorithm that successfully partitions the vertices of a graph sequence into smooth clusters, even when the number of vertices is allowed to vary over time. Our approach uses spectral clustering and relies on applying the k partition problem to a graph constructed from the input graph sequence. Several experiments demonstrate the performance of our method and its advantages over existing methods.

Bai and Hancock recently proposed a novel edge-based matching kernel for graphs [1], by aligning depth-based representations. Unfortunately, one drawback arising in their kernel is the computational inefficiency for large graphs. This follows the fact that their kernel is essentially defined on directed line graphs. Moreover, the computational complexity of the kernel is cubic in the vertex number of the line graph. Since the directed line graph is a dual representation and each vertex represents a directed arc residing on the edge of the original graph. For a graph having n vertices, there may be at most n(n − 1) directed arcs residing on the edges and thus at most n(n − 1) vertices in the directed line graph. As a result, computing the kernel through the line graphs may require time complexity O(n6) for the worst case, making the kernel unapplicable for graphs having hundreds of vertices. The aim of this paper is to overcome this inefficiency, by proposing a new edge-based matching kernel. In order to cope with large graph structures, we propose to construct a sparser version of the original graph using the simplification method introduced in [2]. More specifically, we compute the minimum spanning tree over the commute time matrix of a graph. This spanning tree representation minimizes the number of edges of the original graph while preserving most of its structural information. With this simplification method to hand, the new edge-based matching kernel between two graphs is then computed on the directed line graphs transformed from their respective minimum spanning trees. We show that this strategy significantly reduces the computational complexity to O(n3). We evaluate the performance of the proposed kernels on several standard graph datasets. The experimental results demonstrate the effectiveness and efficiency.

We proposed new analogous results for fuzzy spanning sub graphs, complete, simple, regular and connected fuzzy graphs along with proof. As far as we know, there are no such results available in the previous work.

How to succinctly represent the truly relevant information in big data graphs? The approach presented in this paper aims to discover hidden graph structures and exploit them to compactly summarize large graphs. First, we show that some special graph classes such as cliques and bicliques can be represented efficiently as Pseudo-Boolean (PB) constraints. Then, we propose three new graph classes representable as PB constraints, called nested, sequence and clique-nested bi-partite graphs. Finally, we derive a general approach for partial or complete summarization of an arbitrary graph as a disjunction of PB constraints. Our representation can be seen as an original way to represent the edges of the graph, as they correspond to particular solutions of the PB constraints. An extensive experimental evaluation on several real-world networks shows that our framework is competitive with the state-of-the-art compression technique.

This paper investigates the fundamental limits for compressing random graphs. It also discusses the compression of data on graphs. The graphs are assumed to have labelled vertices. The most basic example is the Erdős-Renyi model, which corresponds to the well-understood case of compressing i.i.d. bits. This paper investigates inhomogeneous random graphs that have clusters, or equivalently, block models. These correspond to mixtures of Erdős-Renyi models for which basic tools for i.i.d.-like sources may not apply, capturing a key feature of general network models. It is shown how the fundamental limit of lossless compression for such models takes different forms as the graph gets sparser. The paper also introduces connections between compression and clustering, how each field can impact the other, and how clustering can help for the compression of data on graphs.

Many chemical compounds can be expressed by a class of graphs called outerplanar graphs. By taking advantage of this tractable class of graphs, we use block preserving outerplanar graph patterns having structured variables for expressing structural features of outerplanar graphs. We propose a method for acquiring characteristic block preserving outerplanar graph patterns from positive and negative outerplanar graph data by Genetic Programming using vertex and edge label information of positive examples. We report experimental results on real chemical compound data.

Graph coloring is a fundamental NP-hard problem in graph theory. It has a wide range of real applications, such as Operations Research, Communication Network, Computational Biology and Compiler Optimization. Notable efforts have been spent on designing its approximation algorithms. Halldrsson proposed the algorithm (denoted as SampleIS) with the current best known approximation ratio. However, its time complexity is O(|G|3), where |G| is the number of vertices of a graph G. It is clear that SampleIS is not practical for large graphs. In this paper, we propose a practical vertex-cut based coloring technique (VColor) for coloring large graphs. First, we partition G into k connected components (CCs) of a small size s by removing a vertex-cut component (VCC). For each CC, we apply our novel coloring algorithm, based on maximal independent set enumeration. The approximation ratio and the time complexity for coloring the k CCs are log s + 1 and O(ks23s/3), respectively, whereas those of SampleIS are ks(log log ks)2/ log3 ks and O(k3s3). For the VCC, we simply apply SampleIS. To combine the colorings of the CCs and the VCC, we propose a maximum matching based algorithm. Second, in the context of a database of graphs, users may color many graphs. We propose an optimization technique, inspired by multi-query optimization, for coloring a set of graphs. We design a VP hierarchy (VPH) to represent the common subgraphs as the common CCs. Third, we propose techniques for determining the optimal values of the parameters of VColor. Our extensive experimental evaluation on real-world graphs confirms the efficiency and/or effectiveness of our proposed techniques. In particular, VColor is more than 500 times faster than SampleIS, and the number of colors used are comparable on real graphs Yeast and LS.

We present a new graph compressor that detects repeating substructures and represents them by grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. For RDF graphs and version graphs it outperforms the best known previous methods. Specific queries such as reachability between two nodes, can be evaluated in linear time over the grammar, thus allowing speed-ups proportional to the compression ratio.

The notion of clique-width for graphs is a relatively new topic which has received attention in the past decade. A graph has bounded clique-width if it can be represented as an algebraic expression on a constant number of labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs with bounded clique-width. Interestingly also, many graph families that arise in practice have bounded clique-width. In this paper, we present compact navigation oracles for graphs with bounded clique-width. Our oracles answer adjacency and neighborhood queries in constant time using O(n) space (i.e., O(n) bits) for a graph of size n, and report the degree of each given vertex, also in constant time, using O(n lg lg n) bits.

We present a greedy approximation algorithm to solve the problem of finding a minimum permanent dominating set for a given dynamic graph represented using the evolving graphs model. The node set of the dynamic graph is static and only the edge set changes with time. All the change information over the lifetime of the dynamic graph is known apriori. The proposed algorithm is an O(ln(nτ))-approximation algorithm, where n is the number of nodes and τ is the lifetime of the dynamic graph.

A set D ? V of a graph G = (V, E) is called an open neighborhood locating-dominating set (OLD-set) if (i) NG (v) n D ? emptyset for all v ? V, and (ii) NG (u)n D? NG (v)n D for every pair of distinct vertices u, v? V. Given a graph G = (V, E), the Min OLD-set problem is to find an OLD-set of minimum cardinality. The cardinality of a minimum OLD-set of G is called the open neighborhood location-domination number of G, and is denoted by ?old (G). Given a graph G and a positive integer k, the Decide OLD-set problem is to decide whether G has an OLD-set of cardinality at most k. The Decide OLD-set problem is known to be NP-complete for bipartite graphs. In this paper, we strengthen this NP-complete result by showing that the Decide OLD-set problem remains NP-complete for perfect elimination bipartite graphs, a subclass of bipartite graphs. Then, we show that the Min OLD-set problem can be solved in polynomial time in chain graphs, a subclass of perfect elimination bipartite graphs. We show that for a graph G, ?old (G)=/2n ?(G) + 2, where n denotes the number of vertices in G, and ? (G) denotes the maximum degree of G. As a consequence we obtain a /? (G) + 2 2-approximation algorithm for the Min OLD-set problem. Finally, we prove that the Min OLD-set problem is APX-complete for chordal graphs with maximum degree 4.

Embedding graphs on the torus is a problem with both theoretical and practical importance. It is required to embed a graph on the torus for solving many application problems such as VLSI design, graph drawing and etc. Polynomial time and exponential time algorithms for embedding graphs on the torus are known. However, the polynomial time algorithms are very complex and their implementation has been a challenge for a long time. On the other hand, the implementations of some exponential time algorithms are known but they are not efficient for large graphs in practice. To develop an efficient practical tool for embedding graphs on the torus, we propose a new exponential time algorithm for embedding graphs on the torus. Compared with a well used previous exponential time algorithm, our algorithm has a better practical running time.

Graph pattern matching is a hot spot in the big data era, which is to find answer graphs matching a given query graph in a data graph of graph databases. "Matching" means two graphs satisfy some relation, such as isomorphism, simulation, bisimulation, etc. Since there are seldom algorithms for the subgraph bisimulation, our work commits to solve the graph pattern matching problem involving bisimulation relations through the model checking technology. We characterize query graphs by modal formulas. By model checking the formulas in the data graphs, the answer graphs bisimilar to the query graphs can be discovered. We add * to basic modal logic language resulting in M L + * language, and add □* to form M L + * formulas. Then a theorem which states that M L + * formulas characterize finite directed graphs modulo bisimulation is put forward. Furthermore, we list steps to find answer graphs bisimilar to a query graph.

We show that there exists a graph $G$ with $O(n)$ nodes, where any forest of $n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant arboricity $k$, the result implies the existence of a graph with $O(n^k)$ nodes that contains all $n$-node graphs as node-induced subgraphs, matching a $\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a $\log_2 n +O(1)$ labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010)., Comment: A preliminary version of this paper appeared at FOCS'15

We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth. We show that all operator fragments of LTL under the investigated parameterisations are intractable in the sense of parameterised complexity., TIME 2015 conference version

Distributed computation on directed graphs has been increasingly important in emerging big data analytics. However, partitioning the huge real-world graphs, such as social and web networks, is known challenging for their skewed (or power-law) degree distributions. In this paper, by investigating two representative k-way balanced edge-cut methods (LDG streaming heuristic and METIS) on 12 real social and web graphs, we empirically find that both LDG and METIS can partition page-level web graphs with extremely high quality, but fail to generate low-cut balanced partitions for social networks and host-level web graphs. Our deep analysis identifies that the global star-motif structures around high-degree vertices is the main obstacle to high-quality partitioning. Based on the empirical study, we further propose a new distributed graph model, namely Agent-Graph, and Agent+ framework that partitions power-law graphs in Agent-Graph model. Agent-Graph is a vertex cut variant in the context of message passing, where any high-degree vertex is factored into arbitrary computational agents in remote partitions for message combining and scattering. Agent framework filters the high-degree vertices to form a residual graph which is then partitioned with high quality by existing edge-cut methods, and finally refills high-degree vertices as agents to construct an agent-graph. Experiments show that the Agent+ approach constantly generates high-quality partitions for all tested real-world skewed graphs. In particular, for 64-way partitioning on social networks and host-level web graphs, the Agent+ approach reduces edge cut equivalently by 27%a#x007E; 79% for LDG and 23%a#x007E;82% for METIS.

A graph is used to represent data in which the relationships between the objects in the data are at least as important as the objects themselves. Large graph datasets are becoming more common as networks such as the Internet grow, and our ability to measure these graphs improves. This necessitates methods to compress these datasets. In this paper we present a method aimed at lossy compression of large, dynamic, weighted graphs.

There are many problems in Graph Theory for finite graphs relating the number of vertices and the number of edges and, therefore, related to the average degree for finite graphs. However, when dealing with real-life problems involving networks, it is often useful to model the situation by using infinite graphs, which can represent extendable systems. In this paper, we will generalize the concept of average degree for infinite graphs in a family of graphs that we call average-measurable. Besides, this new definition allows the generalization of the universal formulae for evaluation of percolation thresholds.

This paper uses a new matrix analysis tool, the semi-tensor product of matrices (STP), to investigate the problem of searching k-internally stable set (k-ISS) and k-maximum internally stable set (k-MISS) of graphs, which serve as mathematical models of analizing many concrete realworld problems such as the k-track assignment problem. By introducing a characteristic vector for vertex subsets of graphs and using the STP, several new sufficient and necessary conditions of the k-ISS and k-MISS are obtained, based on which an algorithm able to find out all k-ISSs and k-MISSs of graphs is established. The results are quite different from existing methods and provide a new angle and means to understand and analyze the structure of graphs. The correctness of the results is finally examined by several illustration examples.

There are several classes of operators on graphs to consider in deciding on a collection of building blocks for graph algorithms. One class involves traditional graph operations such as breadth first or depth first search, finding connected components, spanning trees, cliques and other sub graphs, operations for editing graphs and so on. Another class consists of linear algebra operators where the matrices somehow depend on a graph. It is the latter class of operators that this paper addresses. We describe a least squares formulation on graphs that arises naturally in problems of ranking, distributed clock synchronization, social choice, arbitrage detection, and many other applications. The resulting linear systems are analogous to Poisson's equations. We show experimental evidence that some iterative methods that work very well for continuous domains do not perform well on graphs whereas some such methods continue to work well. By studying graph problems that are analogous to discretizations of partial differential equations (PDEs) one can hope to isolate the specific computational obstacles that graph algorithms present due to absence of spatial locality. In contrast, such locality is inherent in PDE problems on continuous domains. There is also evidence that PDE based methods may suggest improvements suitable for implementation on graphs.

We consider mining dense substructures (maximal cliques) from an uncertain graph, which is a probability distribution on a set of deterministic graphs. For parameter 0 < {\alpha} < 1, we present a precise definition of an {\alpha}-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of {\alpha}-maximal cliques possible within an uncertain graph. We present an algorithm to enumerate {\alpha}-maximal cliques in an uncertain graph whose worst-case runtime is near-optimal, and an experimental evaluation showing the practical utility of the algorithm., Comment: ICDE 2015

Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguna, Vahdat (INFOCOM, pp. 2973–2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of k-cliques E[K k ] and the size of the largest clique ω(G). We observe that there is a phase transition at power-law exponent γ = 3. More precisely, for γ e (2,3) we prove E[K k ] = nk(3-γ)/2 Θ(k)−k and ω(G) = Θ(n(3-γ)/2) while for γ  3 we prove E[K k ] = nΘ(k)−k and ω(G) = Θ(log(n)/log log n). We empirically compare the ω(G) value of several scale-free random graph models with real-world networks. Our experiments show that the ω(G)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.

This paper studies the problem of graph choice in order to maximize consensus convergence speed. Instead of algebraic connectivity, a quadratic criterion is used which is shown to depend on the whole spectrum of the consensus dynamics matrix. The influence of new links to this cost is investigated and a first-order approximation is given. This approximation can be used to compare the effect that different links will have and this is exploited to propose a simple algorithm that starts from a regular lattice and adds links until all nodes have a specific number of neighbours. The resulting graph is compared with random graphs known to have high connectivity because of the small-world effect. Numerical experimentation showed that, for specific parameters, this algorithm provides a graph outperforming a large number of realizations of random graphs both in terms of algebraic connectivity and of the proposed quadratic criterion; for these random graphs it was also shown that this quadratic criterion correlates better with the characteristic path length than algebraic connectivity does.

Static Graphs consist of a fixed sequence of nodes and edges which does not change over time, hence lack in providing the information regarding evolution of the network. In contrast, Dynamic Graphs to a greater extent relate to real-life events and so provide complete information about the network evolution. That is why many researchers [1, 2, 3, 5, 6, 7, 8, 9 and 10] have developed interest in mining of Dynamic Graphs. We feel, that the topic can be further sub-divided structurally into four major categories, which are mining of Labeled, Edge Unlabeled, Directed and Undirected Dynamic Graphs. However, the main focus of research till now is on the mining of Edge Unlabeled Dynamic Graphs. But the limitation is that it does not provide the complete insights of graphs where edge strengths i.e. weights are also changing with time. For example in case of Coauthor network mining in Unlabeled Dynamic Graphs gives information only about the occurrence of relation whereas that in Labeled Dynamic Graphs provides more detailed information like the number of paper published jointly at different instants of time. To address this problem, the present paper proposes a novel method to find out Weighted Regular Patterns in Edge Labeled Dynamic Graphs. The proposed method consists of creating a summary graph to find weight occurrence sequence of edges enabling to determine weighted regular patterns. The method is applied to real world dataset, PACS networks, to ensure its practical feasibility and to understand how Weighted Dynamic Graphs behave regularly over time.

The applications of the sub graph isomorphism search are growing with the growing number of areas that model their systems using graphs or networks. Specifically, many biological systems, such as protein interaction networks, molecular structures and protein contact maps, are modeled as graphs. The sub graph isomorphism search is concerned with finding all sub graphs that are isomorphic to a relevant query graph, the existence of such sub graphs can reflect on the characteristics of the modeled system. The most computationally expensive step in the search for isomorphic sub graphs is the backtracking algorithm that traverses the nodes of the target graph. In this paper, we propose a pruning approach that is inspired by the minimum remaining value heuristic that achieves greater scalability over large query and target graphs. Our testing on various biological networks shows that performance enhancement of our approach over existing state-of-the-art approaches varies between 6x and 53x.

© 2014 IEEE. Graph classification has traditionally focused on graphs generated from a single feature view. In many applications, it is common to have useful information from different channels/views to describe objects, which naturally results in a new representation with multiple graphs generated from different feature views being used to describe one object. In this paper, we formulate a new Multi-Graph-View learning task for graph classification, where each object to be classified contains graphs from multiple graph-views. This problem setting is essentially different from traditional single-graph-view graph classification, where graphs are from one single feature view. To solve the problem, we propose a Cross Graph-View Sub graph Feature based Learning (gCGVFL) algorithm that explores an optimal set of sub graphs, across multiple graph-views, as features to represent graphs. Specifically, we derive an evaluation criterion to estimate the discriminative power and the redundancy of sub graph features across all views, and assign proper weight values to each view to indicate its importance for graph classification. The iterative cross graph-view sub graph scoring and graph-view weight updating form a closed loop to find optimal sub graphs to represent graphs for multi-graph-view learning. Experiments and comparisons on real-world tasks demonstrate the algorithm's performance.

Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.

Graph evolution - evolving a graph or network to fit specific criteria - is a recent enterprise because of the difficulty of representing a graph in an easily evolvable form. Simple, obvious representations such as adjacency matrices can prove to be very hard to evolve and some easy-to-evolve representations place severe limits on the space of graphs that is explored. This study fills in a gap in the literature by presenting two scalable families of benchmark functions. These functions are tested on a number of representations. The first family of benchmark functions is matching the eccentricity sequences of graphs, the second is locating graphs that are relatively easy to color non-optimally. One hundred examples of the eccentricity sequence matching problem are tested. The examples have a difficulty, measured in time to solution, that varies through four orders of magnitude, demonstrating that this test problem exhibits scalability even within a particular size of problem. The ordering by problem hardness, for different representations, varies significantly from representation to representation. For the difficult coloring problem, a parameter study is presented demonstrating that the problem exhibits very different results for different algorithm parameters, demonstrating its effectiveness as a benchmark problem.

Network structure is irregular, complex and dynamically evolving in time. Labelled graphs are used in researching areas of many networks, cryptography, computer science, biology, information etc. For simulating real networks we construct several classes of sun-like network models, and show that sun-like network models have can be strictly distinguished by odd-elegant labellings. We have several algorithms in polynomial time.

Motivated by improving the efficiency of pattern matching on graphs, we define a new kind of equivalence on graph vertices. Since it can be used in various graph algorithms that explore graphs, we call it exploratory equivalence. The equivalence is based on graph automorphisms. Because many similar equivalences exist (some also based on automorphisms), we argue that this one is novel. For each graph, there are many possible exploratory equivalences, but for improving the efficiency of the exploration, some are better than others. To this end, we define a goal function that models the reduction of the search space in such algorithms. We describe two greedy algorithms for the underlying optimization problem. One is based directly on the definition using a straightforward greedy criterion, whereas the second one uses several practical speedups and a different greedy criterion. Finally, we demonstrate the huge impact of exploratory equivalence on a real application, i.e., graph grammar parsing.

In this paper, we aim to characterize hyper graphs in terms of structural complexities. To measure the complexity of a hyper graph in a straightforward way, we transform a hyper graph into a line graph which accurately reflects the multiple relationships exhibited by the hyper graph. To locate the dominant substructure within a line graph, we identify a centroid vertex by computing the minimum variance of its shortest path lengths. A family of directed centroid expansion sub graphs of the line graph is then derived from the centroid vertex. We compute the directed depth-based complexity trace of a hyper graph by measuring directed entropies on its directed sub graphs. The novel hyper graph complexity trace provides a flexible framework that can be applied to both hyper graphs and graphs. Experiments on standard (hyper)graph datasets demonstrate the effectiveness and efficiency of the new complexity trace.

In this paper, we present a hyper graph kernel computed using substructure isomorphism tests. Measuring the isomorphisms between hyper graphs straightforwardly tends to be elusive since a hyper graph may exhibit varying relational orders. We thus transform a hyper graph into a directed line graph. This not only accurately reflects the multiple relationships exhibited by the hyper graph but is also easier to manipulate isomorphism tests. To locate the isomorphisms between hyper graphs through their directed line graphs, we propose a new directed Weisfeiler-Lehman isomorphism test for directed graphs. The new isomorphism test precisely reflects the structure of the directed edges. By identifying the isomorphic substructures of directed graphs, the hyper graph kernel for a pair of hyper graphs is computed by counting the number of pair wise isomorphic substructures from their directed line graphs. We show that our kernel limits tottering that arises in the existing walk and sub tree based (hyper)graph kernels. Experiments on challenging (hyper)graph datasets demonstrate the effectiveness of our kernel.

In this paper, we study the graph clustering (partition) problem. The problem is to determine whether there is a partition of the vertices of a graph into certain number of clusters such that the diameter of subgraph induced by each cluster does not exceed a prescribed bound. An amusing result shows that for chordal graphs (respectively, dually chordal graphs) the problem is NP-complete if the diameter bound is restricted to any even integer (respectively, to any odd integer); otherwise, the problem is polynomial solvable for both classes of graphs. Moreover, by a simple reduction using graph powers, we show that there is a unified approach for solving this problem in various graph classes, including distance-hereditary graphs, doubly chordal graphs, circular-arc graphs, and AT-free graphs.

Rectangles are the smallest cycles (i.e., cycles of length 4) and most elementary sub-structures in a bipartite graph. Similar to triangle counting in uni-partite graphs, rectangle counting has many important applications where data is modeled as bipartite graphs. However, efficient algorithms for rectangle counting are lacking. We propose three different types of algorithms to cope with different data volumes and the availability of computing resources. We verified the efficiency of our algorithms with experiments on both large real-world and synthetic bipartite graphs.

Many recent literature show that labelled graphs can be applied in a wide range of scientific fields, such as coding theory, communication network, logistic and so on. For the purpose of researching complex networks, we define irregular dragon graphs as new network models, and show that irregular dragon graphs admit odd-graceful labellings.

Can we model complex networks as hyper graphs and compress them for faster storage, transmission, and mining of data? In this paper, we propose a modeling and compression technique that consists of two phases: (i) mapping networks to hyper graphs by exploiting inherent or structural semantic features, and (ii) partitioning the resulting hyper graph such that similar nodes are grouped into a number of possibly disconnected parts. The partitioned hyper graph is then processed in order to yield more structural redundancy to increase compression. We provide empirical results that compare the proposed method to random and natural orderings of select real networks using an information-theoretic measure. When modeling networks using hyper graphs as proposed here, the potential for compactness and compression increases, as observed in our experimental evaluation. This benefits a variety of domains in a variety of ways, such as social networks, biological systems, and the need to represent these as compactly as possible for faster execution of queries. We also address questions for eventual investigation.

Finding a maximal independent set (MIS) is a classic problem in graph theory that has been widely studied in the context of distributed algorithms. Standard distributed solutions to the MIS problem focus on time complexity. In this paper, we also consider fairness. For a given MIS algorithm A and graph G, we define the inequality factor for A on G to be the largest ratio between the probabilities of the nodes joining an MIS in the graph. We say an algorithm is fair with respect to a family of graphs if it achieves a constant inequality factor for all graphs in the family. In this paper, we seek efficient and fair algorithms for common graph families. We begin by describing an algorithm that is fair and runs in O(log* n)-time in rooted trees of size n. Moving to unrooted trees, we describe a fair algorithm that runs in O(log n) time. Generalizing further to bipartite graphs, we describe a third fair algorithm that requires O(log2 n) rounds. We also show a fair algorithm for planar graphs that runs in O(log2 n) rounds, and describe an algorithm that can be run in any graph, yielding good bounds on inequality in regions that can be efficiently colored with a small number of colors. We conclude our theoretical analysis with a lower bound that identifies a graph where all MIS algorithms achieve an inequality bound in Ω(n)-eliminating the possibility of an MIS algorithm that is fair in all graphs. Finally, to motivate the need for provable fairness guarantees, we simulate both our tree algorithm and Luby's MIS algorithm [13] in a variety of different tree topologies-some synthetic and some derived from real world data. Whereas our algorithm always yield an inequality factor ≤3.25 in these simulations, Luby's algorithms yields factors as large as 168.

We improve the best previously-known lower bound on the size of largest homometric sets in sparse diameter-two graphs. Along with the proof, we provide a method for constructing the desired homometric sets. We also study outerplanar graphs and show how to construct homometric sets in a given outerplanar graph of the size at least clogn, where n is the number of vertices in the graph, and c a positive fixed constant.

The localization of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. We will address the localization of a cluster of activity in Gaussian noise in directed, weighted graphs. We develop a penalized likelihood estimator (we call the relaxed graph scan) as a relaxation of the NP-hard graph scan statistic. We review how the relaxed graph scan (RGS) can be solved using graph cuts, and outline the max-flow min-cut duality. We use this combinatorial duality to derive a path algorithm for the RGS by solving successive max flows. We demonstrate the effectiveness of the RGS on two simulations, over an undirected and directed graph.

Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many graph problems that are NP-hard in general case have polynomial time algorithms for trapezoid graphs. A matching in a graph is a set of pairwise non-adjacent edges, and a maximum matching is a matching whose cardinality is maximum. In this paper, we define a modified range tree data structure, called S-Range tree, which allows to report the maximum label of points in a rectangular region and update the label of a point efficiently. We use this data structure to construct an O(n(log n)3) algorithm for finding a maximum matching in trapezoid graphs based on their box representation. In addition, we generalize this algorithm for a larger graph class, k-trapezoid graph by using multidimensional range tree. To the best of our knowledge, this is the first efficient maximum matching algorithm for trapezoid graphs.