# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 1 Introduction  
Networks, or in mathematical terms, graphs, are the standard tool to model interactions between entities. These entities may stem from virtually every application domain. They may be, for example, proteins that interact physically within a cell [1], people in social networks [2] or websites that are connected via hyperlinks [3]. A standard task in the analysis of these networks is to identify subnetworks that correspond to a cohesive group of entities, also called a community, in the scenario modeled by the network. Consider, for example, a group of tribes in the highlands of New Guinea that was studied by [PERSON] [4]. To gain an overview of the relationships between these tribes, [PERSON] [4] determined in a field study for pairs of tribes whether they have a friendly or hostile relationship and summarized these data in a social network. Figure 1 shows a part of this network where edges signify a friendly relationship between two tribes (we omit the hostile relationships). To better understand the society of the highland tribes, one might be interested in determining whether there are any communities of friendly tribes in this network. The most obvious approach to model such a community is to demand that all members of the community have a friendly relationship. In graph-theoretic terminology, such communities are called _cliques_. **Definition 1**. : A set \(S\) in a graph \(G=(V,E)\) is a _clique_ if each pair of vertices \(u,v\in S\) is adjacent. Clique  
**Input:** An undirected graph \(G=(V,E)\) and an integer \(k\). **Question:** Does \(G\) contain a clique of size \(k\)? The maximum clique of the example social network is also shown in Figure 1. Using the clique definition as the community model, this set of vertices would be a predicted community. In most applications, however, using cliques as a community model is inappropriate. The Clique Model is Usually Too Strict  
There are two reasons why this is the case. First, the data collection is usually subject to noise. In the example, this could be the case if the researcher misinterpreted the relationships between some tribes. Thus, even if cliques are the correct model for communities, the real communities will not appear as cliques in the network, because some edges are missing due to noise. The second issue, which cannot be avoided by being more careful in the data collection, is that in many scenarios, it may be allowed that not all members of a community have to interact with each other. In the example network, the \"Ove\" and \"Geham\" tribes have no friendly relationship with each other. This is not necessarily a sign of a hostile relationship, but, as a geographic overview over the areas settled by the tribes suggests [4], is simply due to the fact that these two tribes are not geographic neighbors. Nevertheless, these two tribes may belong to the same community, for example because they have friendly relations with all common neighbors. Thus, a community may not necessarily appear as a clique in the network, but it may fulfill certain less strict cohesiveness properties. Clique Relaxations  
To overcome the modeling drawbacks of cliques, one can replace the clique model with a _clique relaxation_. As the name suggests, this is a model that relaxes one or more _clique-defining_ properties [5]. These are properties that are only fulfilled by cliques. In particular, we consider models relaxing the following clique-defining properties:  
_Clique definition via vertex degrees_: A size-\(k\) set \(S\) in a graph \(G\) is a clique if and only if every vertex \(v\in S\) has degree \(k-1\) in \(G[S]\), the subgraph induced by \(S\). Figure 1: A part of the highland tribes social network [4]. The black vertices form the maximum clique in this network. _Clique definition via diameter_: A size-\(k\) set \(S\) in a graph \(G\) is a clique if and only if \(G[S]\) has diameter one, that is, there is a path consisting of one edge between every pair of vertices in \(S\).