Project topics and materials
Get Complete Project Material File(s) Now! »
Extensions of the Decomposition
In the literature there is a research effort to introduce new graph decompo-sitions inspired by the degeneracy framework. This is as well one of our main concerns throughout the whole thesis. One of those decompositions that is worth mentioning is the k-truss decomposition. It is in fact the k-core decompo-sition of the line graph studied, i.e a k-truss in a graph is a subset of the graph such that every edge in the subject is supported by at least k2 other edges that form triangles with that particular edge Figure 2.4. In other words, every edge in the truss must be part of k2 triangles made up of nodes that are part of the truss.
Comments and Precisions
The previously defined concepts and objects will be widely used, at least for a majority of them, in the rest of the dissertation. It is important to note that we will work exclusively on undirected graphs, that will have some given pro-perties depending on the application. As shown in the previous section, k-core as it is defined is applied to undirected graphs, but can also work in the same manner on edge weighted graphs, where nodes have weighted degree. Moreo-ver, for bipartite graphs, k-core decomposition is known to work poorly as we might need a core decomposition on only one side of the bipartite graph (this will be extensively studied in Chapter 6). Finally, except for Chapter 5, where k-core decomposition is used as a tool, capitalizing on the properties we learnt in the previous sections. The focus of our work will be, in Chapter 3, to study and explain theoretical properties on the degeneracy and generalised concepts of degeneracy, namely the s-degeneracy. This motivates then our main goal, that is building equivalent theoretical results, and unify degree degeneracy and connectivity degeneracy hierarchies under a single framework that ease the generation of such decompositions. We then experiment on one of these de-compositions, namely the 1-edge-connectivity degeneracy, comparing it to the k-core and k-truss decompositions, on real-world scenarios (studied in Chap-ter 4). It is important, to avoid any further confusion, to distinguish s-degeneracy and k-core, i.e. the k-core framework corresponds to the 1-degeneracy. This will be extensively developed in Chapter 3 and after this chapter we will only deal with k-core, k-truss, or the later defined k-edge-connectivity core.
Graph Searching and s-edge-degeneracy
The study of graph searching parameters is an active field of graph theory. Several important graph parameters have their search-game analogues that provide useful insights on their combinatorial and algorithmic properties. (For related surveys, see [Fomin and Thilikos, 2008, Bienstock, 1991, Fomin and Petrov, 1996, Alspach, 2004, Alpern and Gal, 2003].) We introduce a graph searching game, where the opponents are a group of cops and a robber. In this game, the cops are blocking edges of the graph, while the robber resides on the vertices. The first move of the game is done by the robber, who chooses a vertex to occupy. Then, the game is played in rounds. In each round, first the cops block a set of edges and next the robber moves to another vertex via a path consisting of at most s unblocked edges. The robber cannot stay put and he/she is captured if, after the move of the cops, all the edges incident to his/her current location are blocked. Both cops and robbers have full knowledge of their opponent’s current position and they take it into consideration before they make their next move. We next give the formal definition of the game. The game is parameterized by the speed s 2 N+1 of the robber. A search strategy on G for the cops is a function f : V (G) ! 2E(G) that, given the current position x 2 V (G) of the robber in the end of a round, outputs the set f(v) of the edges that should be blocked in the beginning of the next round. The cost of a cop strategy f is defined as cost(f) = maxfjf(v)j j v 2 V (G)g, i.e., the maximum number of edges that may be blocked by the robbers according to f.
An escape strategy on G for the robber is a pair R = (vstart; g) where vstart is the vertex of robber’s first move and g : 2E(G) V (G) ! V (G) is a function that, given the set F of blocked edges in the beginning of a round and the current position x of the robber, outputs the vertex u = g(F; v) where the robber should move. Here the natural restriction for g is that there is an s-path from v to u in G n F . Clearly, if F is the set of edges that are incident to v, then g(F; v) should be equal to v and this expresses the situation where the robber is captured. Let f and R = (vstart; g) be strategies for the cop and the robber respecti-vely. The game scenario generated by the pair (f; R) is the infinite sequence v0; F1; v1; F2; v2; : : : ; where v0 = vstart and for every i 2 N 1, Fi = f(vi 1) and vi = g(Fi; vi 1). If vi = vi 1 for some i 2 N 1, then (f; R) is a cop-winning pair, otherwise it is a robber-winning pair. The capture cost against a robber of speed s in a graph G, denoted by ccs(G) is the minimum k for which there is a cop strategy f, of cost at most k, such that for every robber strategy R, (f; R) is a cop-winning pair.
A Min-max Theorem For s-edge-degeneracy
Definition 3.3.1 (edge-separator and support). Let G be a graph, x 2 V (G), S V (G) n fxg, and s 2 N+1. We say that a set A E(G) is an (s; x; S)-edge-separator if every s-path of G from x to some vertex in S, contains some edge from A. We define suppG;s(x; S) to be the minimum size of an (s; x; S)-edge-separator in G. Let G be a graph and let L = hv1; : : : ; vri be a layout (i.e. linear ordering) of its vertices. Given an i 2 [r]; we denote L i = hv1; : : : ; vii. Given an s 2 N+1, we define the s-edge-support of a vertex vi in L as suppG;s(vi; L i 1). Definition 3.3.2 (s-edge-degeneracy). The s-edge-degeneracy of L, is the maxi-mum s-edge-support of a vertex in L. The s-edge-degeneracy of G, denoted by es(G) is the minimum s-edge-degeneracy over all layouts of G. Definition 3.3.3 ((k; s)-edge-hide-outs). edge-hide-out in a graph G is any set R suppG;s(x; R n fxg) k. Let s 2 N+1 and k 2 N. A (k; s)-V (G) such that, for every x 2 R, A (k; s)-edge-hide-out S is maximal if there is no other (k; s)-edge-hide-out S0 with S ( S0. It is easy to verify that every graph contains a unique maximal (k; s)-edge-hide-out.
Table of contents :
Abstract
R´esum´e
List of Publications
1 Introduction
1.1 Thesis Statement and Research Drives
1.2 Outline of the Thesis and Contributions
2 Basic Notations and Definitions
2.1 Graphs, Notations and Types
2.2 Graph Functions and Properties
2.2.1 Degeneracy and k-core Decomposition
2.2.2 Extensions of the Decomposition
2.3 Comments and Precisions
3 Edge Degeneracy : Algorithmic and Structural Results
3.1 Introduction
3.2 Basic Definitions
3.3 Graph Searching and s-edge-degeneracy
3.3.1 A Search Game
3.3.2 A Min-max Theorem For s-edge-degeneracy
3.3.3 The Complexity of s-edge-degeneracy, for Distinct Values of s
3.4 A structural Theorem for Edge-admissibility
3.4.1 Basic Definitions
3.4.2 A Structural Characterizations of k-immersion Free Graphs
3.4.3 An Upper Bound to Edge-admissibility
3.5 Conclusion
4 Degeneracy Hierarchy Generators and Efficient Algorithm for Edge Connectivity Degeneracy
4.1 Introduction
4.2 Preliminary Definitions
4.2.1 s(-edge)-degeneracy and s(-edge)-admissibility
4.2.2 k-blocks and Carving Decompositions
4.2.3 s(-edge)-connectivity Degeneracy and s(-edge)-connectivity
4.3 Connectivity Degeneracy versus Degree Degeneracy
4.3.1 Degeneracy Hierarchies Generator
4.3.2 s-degeneracy and s-admissibility Comparison
4.3.3 Relation Between Degree and Connectivity
4.4 Algorithm Design for k-Edge-Connectivity Degeneracy
4.4.1 Properties and Heuristics
4.4.2 Algorithm Design
4.5 Experiments
4.5.1 Tree-like Decomposition versus Nested One
4.5.2 Epidemic Models
4.5.3 Datasets
4.5.4 Results
4.6 Conclusion
5 A Degeneracy Framework for Graph Similarity
5.1 Introduction
5.2 Preliminaries
5.2.1 Definitions and Notations
5.2.2 Base Kernels
5.3 Degeneracy Framework
5.3.1 Core-based Graph Kernels
5.3.2 Computational Complexity
5.3.3 Dimensionality Reduction Perspective
5.4 Experiments and Evaluation
5.4.1 Datasets
5.4.2 Experimental Setup
5.4.3 Results
5.5 Conclusion
6 Hcore-Init : Graph Degeneracy based Neural Network Initialization
6.1 Introduction
6.2 Preliminaries
6.2.1 Initialization Methods
6.2.2 Hypergraphs and Bipartite Graphs
6.3 Graph Extraction from Neural Network Architecture
6.3.1 Fully-Connected Neural Networks
6.3.2 Convolutional Neural Networks
6.4 Weight Initialization Based on Hcore
6.4.1 Initialization of the FCNN
6.4.2 Initialization of the CNN
6.5 Experiments
6.5.1 Dataset Specifications
6.5.2 Model Setup and Baseline
6.5.3 Settings of the Weight Initialization
6.6 Conclusion
7 Conclusion
7.1 Summary of Contributions
7.2 Future Directions of Research
7.3 Epilogue
Bibliography
