Detecting Cohesive Subgraphs
Benjamin McClosky, Illya V. Hicks · 2008
All graphs in this paper are finite, simple, and undirected. A complete graph consists of pairwise adjacent vertices. A maximal complete subgraph defines a clique. The problem of finding maximum cardinality cliques is a classic NP-complete problem and is of fundamental importance in combinatorial optimization. The Maximum Clique Problem (MCP) has applications in ad hoc wireless networks (Chen et al. 2004), data mining (Washio and Motoda 2003), social network analysis (Wasserman and Faust 1994), and biochemistry and genomics (Butenko and Wilhelm 2006). MCP is also related to the derivation of a class of inequalities for general integer programs (Atamturk et al. 2000). In each of these applications, cliques provide a framework for detecting cohesion, or mutual adjacency among a set of vertices. This framework has limitations. For example, consider the graph H in Figure 1. A maximum cardinality clique in H has three vertices, denoted by ω(H) = 3. However, H has multiple subgraphs which are one edge short of defining a larger clique. The maximum clique approach fails to detect this cohesive structure because it only recognizes subgraphs with the highest possible level of cohesion. Seidman and Foster (1978) introduced k-plexes to address this issue. In order to define k-plexes, consider a graph G = (V, E) and vertex v ∈ V . Define NG(v) := {u ∈ V : uv ∈ E}, degG(v) := |NG(v)|, ∆(G) := maxv∈V degG(v), and δ(G) := minv∈V degG(v). Let G[K] denote the subgraph induced by K ⊆ V . Define Ḡ = (V, Ē) to be the complement of G, where e ∈ Ē ⇔ e $∈ E. In this paper, k ≥ 1 is a positive integer.