In this dissertation we consider the problem of mining cohesive (dense) subgraphs in probabilistic graphs, where each edge has a probability of existence. Mining probabilistic graphs has become the focus of interest in analyzing many real-world datasets, such as social, trust, communication, and biological networks due to the intrinsic uncertainty present in them. Studying cohesive subgraphs can reveal important information about connectivity, centrality, and robustness of the network, with applications in areas such as bioinformatics and social networks. In deterministic graphs, there exists various definitions of cohesive substructures, including cliques, quasi-cliques, k-cores and k-trusses. In this regard, k-core and k-truss decompositions are popular tools for finding cohesive subgraphs. In deterministic graphs, a k-core is the largest subgraph in which each vertex has at least k neighbors, and a k-truss is the largest subgraph whose edges are contained in at least k triangles (or k-2 triangles depending on the definition). The k-core and k-truss decomposition in deterministic graphs have been thoroughly studied in the literature. However, in the probabilistic context, the computation is challenging and state-of-art approaches are not scalable to large graphs. The main challenge is efficient computation of the tail probabilities of vertex degrees and triangle count of edges in probabilistic graphs. We employ a special version of central limit theorem (CLT) to obtain the tail probabilities efficiently. Based on our CLT approach we propose peeling algorithms for core and truss decomposition of a probabilistic graph that scales to very large graphs and offers significant improvement over state-of-the-art approaches. Moreover, we propose a second algorithm for probabilistic core decomposition that can handle graphs not fitting in memory by processing them sequentially one vertex at a time. In terms of truss decomposition, we design a second method which is based on progressive tightening of the estimate of the truss value of each edge based on h-index computation and novel use of dynamic programming. We provide extensive experimental results to show the efficiency of the proposed algorithms. Another contribution of this thesis is mining cohesive subgraphs using the recent notion of nucleus decomposition introduced by Sariyuce et al. Nucleus decomposition is based on higher order structures such as cliques nested in other cliques. Nucleus decomposition can reveal interesting subgraphs that can be missed by core and truss decompositions. In this dissertation, we present nucleus decomposition for probabilistic graphs. The major questions we address are: How to define meaningfully nucleus decomposition in probabilistic graphs? How hard is computing nucleus decomposition in probabilistic graphs? Can we devise efficient algorithms for exact or approximate nucleus decomposition in large graphs? We present three natural definitions of nucleus decomposition in probabilistic graphs: local, global, and weakly-global. We show that the local version is in PTIME, whereas global and weakly-global are #P-hard and NP-hard, respectively. We present an efficient and exact dynamic programming approach for the local case. Further, we present statistical approximations that can scale to bigger datasets without much loss of accuracy. For global and weakly-global decompositions we complement our intractability results by proposing efficient algorithms that give approximate solutions based on search space pruning and Monte-Carlo sampling. Extensive experiments show the scalability and efficiency of our algorithms. Compared to probabilistic core and truss decompositions, nucleus decomposition significantly outperforms in terms of density and clustering metrics. / Graduate

In the game of Kal-toh depicted in the television series Star Trek: Voyager, players attempt to create polyhedra by adding to a jumbled collection of metal rods. Inspired by this fictional game, we formulate graph-theoretical questions about polyhedral (triconnected and planar) subgraphs in an on-line environment. The problem of determining the existence of a polyhedral subgraph within a graph G is shown to be NP-hard, and we also give some non-trivial upper bounds for the problem of determining the minimum number of edge additions necessary to guarantee the existence of a polyhedral subgraph in G. A two-player formulation of Kal-toh is also explored, in which the first player to form a target subgraph is declared the winner. We show a polynomial-time solution for simple cases of this game but conjecture that the general problem is NP-hard.

In the game of Kal-toh depicted in the television series Star Trek: Voyager, players attempt to create polyhedra by adding to a jumbled collection of metal rods. Inspired by this fictional game, we formulate graph-theoretical questions about polyhedral (triconnected and planar) subgraphs in an on-line environment. The problem of determining the existence of a polyhedral subgraph within a graph G is shown to be NP-hard, and we also give some non-trivial upper bounds for the problem of determining the minimum number of edge additions necessary to guarantee the existence of a polyhedral subgraph in G. A two-player formulation of Kal-toh is also explored, in which the first player to form a target subgraph is declared the winner. We show a polynomial-time solution for simple cases of this game but conjecture that the general problem is NP-hard.

Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.

No description available.

Forbidding and enforcing systems (fe-systems) provide a new way of defining classes of structures based on boundary conditions. Forbidding and enforcing systems on formal languages were inspired by molecular reactions and DNA computing. Initially, they were used to define new classes of languages (fe-families) based on forbidden subwords and enforced words. This paper considers a metric on languages and proves that the metric space obtained is homeomorphic to the Cantor space. This work studies Chomsky classes of families as subspaces and shows they are neither closed nor open. The paper investigates the fe-families as subspaces and proves the necessary and sufficient conditions for the fe-families to be open. Consequently, this proves that fe-systems define classes of languages different than Chomsky hierarchy. This work shows a characterization of continuous functions through fe-systems and includes results about homomorphic images of fe-families. This paper introduces a new notion of connecting graphs and a new way to study classes of graphs. Forbidding-enforcing systems on graphs define classes of graphs based on forbidden subgraphs and enforced subgraphs. Using fe-systems, the paper characterizes known classes of graphs, such as paths, cycles, trees, complete graphs and k-regular graphs. Several normal forms for forbidding and enforced sets are stated and proved. This work introduces the notion of forbidding and enforcing to posets where fe-systems are used to define families of subsets of a given poset, which in some sense generalizes language fe-systems. Poset fe-systems are, also, used to define a single subset of elements satisfying the forbidding and enforcing constraints. The latter generalizes graph fe-systems to an extent, but defines new classes of structures based on weak enforcing. Some properties of poset fe-systems are investigated. A series of normal forms for forbidding and enforcing sets is presented. This work ends with examples illustrating the computational potential of fe-systems. The process of cutting DNA by an enzyme and ligating is modeled in the setting of language fe-systems. The potential for use of fe-systems in information processing is illustrated by defining the solutions to the k-colorability problem.

Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3. The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.

In recent years, concerns of privacy have become more prominent for social networks. Anonymizing a graph meaningfully is a challenging problem, as the original graph properties must be preserved as well as possible. We introduce a generalization of the degree anonymization problem posed by Liu and Terzi. In this problem, our goal is to anonymize a given subset of vertices in a graph while adding the fewest possible number of edges. We examine different approaches to solving the problem, one of which finds a degree-constrained subgraph to determine which edges to add within the given subset and another that uses a greedy approach that is not optimal, but is more efficient in space and time. The main contribution of this thesis is an efficient algorithm for this problem by exploring its connection with the degree-constrained subgraph problem. Our experimental results show that our algorithms perform very well on many instances of social network data. / Graduate

We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups (up to four elements). Next we describe quasigroups whose power graphs are directed paths, directed cycles, in-stars, out-stars, and empty. We do so by specifying partial Cayley tables, which cannot always be completed in small examples. We then consider sinks in the power graph of a quasigroup, as subquasigroups give rise to sinks. We show that certain structures cannot occur as sinks in the power graph of a quasigroup. More generally, we show that certain highly connected substructures must have edges leading out of the substructure. We briefly comment on power graphs of Bol loops.

Let H be a graph. G is a subgraph of H if V (G) ⊆ V (H) and E(G) ⊆ E(H). The subgraphs of H can be used to determine whether H is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As a cycle with at least four vertices is a canonical example of a triangle-free subgraph, we concentrate our efforts on these. In this thesis, we will state necessary and sufficient conditions for the existence of edge induced and vertex induced cycles within circulants.