6 Local Density

Sven Kosub

Actors in networks usually do not act alone. By a selective process of establishing relationships with other actors, they form groups. The groups are typically founded by common goals, interests, preferences or other similarities. Standard examples include personal acquaintance relations, collaborative relations in several social domains, and coalitions or contractual relationships in markets. The cohesion inside these groups enables them to inuence the functionality of the whole network. Discovering cohesive groups is a fundamental aspect in network analysis. For a computational treatment, we need formal concepts reecting some intuitive meaning of cohesiveness. At a general level, the following characteristics have been attributed to cohesive groups [569]: Mutuality: Group members choose each other to be included in the group. In a graph-theoretical sense, this means that they are adjacent. Compactness: Group members are well reachable for each other, though not necessarily adjacent. Graph-theoretically, this comes in two avors: being well reachable can be interpreted as having short distances or high connectivity. Density: Group members have many contacts to each other. In terms of graph theory, that is group members have a large neighborhood inside the group. Separation: Group members have more contacts inside the group than outside. Depending on the network in question, diverse concepts can be employed, incorporating cohesiveness characteristics with dierent emphases. Notions where density is a dominant aspect are of particular importance. Density has an outstanding relevance in social networks. On the one hand, recent studies have found that social networks show assortative mixing on vertices [441, 444, 446], i.e, they tend to have the property that neighbors of vertices with high degree have also high degree. Assortative mixing is an expression of the typical observation that social networks are structured by groups of high density.1 On the other hand, there are several mathematical results demonstrating that high density implies the other characteristics of cohesiveness. For instance, one classical result [431] says that if each member of a group shares ties with at least
1

Assortativity is now considered as one statistical criterion separating social networks and non-social networks [446]. For instance, some experimental analyses have shown that in the Internet at the level of autonomous systems, the mean degree of the neighbors of an autonomous system with k neighbors is approximately k1/2 [468]. At this level, the Internet is disassortatively mixed.

U. Brandes and T. Erlebach (Eds.): Network Analysis, LNCS 3418, pp. 112142, 2005. c Springer-Verlag Berlin Heidelberg 2005

6 Local Density

113

1 a k -fraction of the other members of the group, then the tie distance within the group is at most k. Results comparable to that can be proven for connectivity as well. Here, however, the dependency from density is not as strong as in the case of distances (see Chapter 7). In this chapter, we survey computational approaches and solutions for discovering locally dense groups. A graph-theoretical group property is local if it is denable over subgraphs induced by the groups only. Locality does not correspond to the above-mentioned separation characteristic of cohesiveness, since it neglects the network outside the group. In fact, most notions that have been dened to cover cohesiveness have a maximality condition. That is, they require for a group to be cohesive with respect to some property , in addition to fullling , that it is not contained in any larger group of the network that satises as well. Maximality is non-local. We present the notions on the basis of their underlying graph-theoretical properties and without the additional maximality requirements. Instead, maximality appears in connection with several computational problems derived from these notions. This is not a conceptual loss. Actually, it emphasizes that locality reects an important hidden aspect of cohesive groups: being invariant under network changes outside the group. Interior robustness and stability is an inherent quality of groups. Non-local density notions and the corresponding algorithmic problems and solutions are presented in Chapter 8. A short list of frequently used non-local notions is also discussed in Section 6.4. The prototype of a cohesive group is the clique. Since its introduction into sociology in 1949 [401], numerous eorts in combinatorial optimization and algorithms have been dedicated to solving computational problems for cliques. Therefore, the treatment of algorithms and hardness results for clique problems deserves a large part of this chapter. We present some landmark results in detail in Section 6.1. All other notions that we discuss are relaxations of the clique concept. We make a distinction between structural and statistical relaxations. A characteristic of structural densities is that all members of a group have to satisfy the same requirement for group membership. These notions (plexes, cores) admit strong statements about the structure within the group. Structurally dense groups are discussed in Section 6.2. In contrast, statistical densities average over members of a group. That is, the property that denes group membership needs only be satised in average (or expectation) over all group members. In general, statistically dense groups reveal only few insights into the group structure. However, statistical densities can be applied under information uncertainty. They are discussed in Section 6.3. All algorithms are presented for the case of unweighted, undirected simple graphs exclusively. Mostly, they can be readily translated for directed or weighted graphs. In some exceptional cases where new ideas are needed, we mention these explicitly.

114

S. Kosub

6.1

Perfectly Dense Groups: Cliques

The graph with perfect cohesion is the clique [401]. Denition 6.1.1. Let G = (V, E) be an undirected graph. A subset U V is said to be a clique if and only if G[U ] is a complete graph. In a clique, each member has ties with each other member. A clique U is a maximal clique in a graph G = (V, E) if and only if there is no clique U in G with U U . A clique is a maximum clique in graph G if and only if it has maximum cardinality among all cliques in G. The striking reasons for perfectness of cliques as cohesive structures are obvious: 1. Cliques are perfectly dense, i.e., if U is a clique of size k, then (G[U ]) = d(G[U ]) = (G[U ]) = k 1. A higher degree is not possible. 2. Cliques are perfectly compact, i.e., diam(G[U ]) = 1. A shorter distance between any two vertices is not possible. 3. Cliques are perfectly connected, i.e., if U is a clique of size k, then U is (k 1)-vertex-connected and (k 1)-edge-connected. A higher connectivity is not possible. The structural properties of a clique are very strong. In real-world settings, large cliques thus should be rarely observable. The famous theorem of Turn a [554] gives precise sucient conditions for the guaranteed existence of cliques of certain sizes with respect to the size of the entire network. Theorem 6.1.2 (Turn, 1941). Let G = (V, E) be an undirected graph. If a 2 m > n k2 , then there exists a clique of size k within G. 2 k1 An immediate consequence of this theorem is that a network itself needs to be dense in order to surely possess a large clique. However, as social networks are usually sparse, we have no a priori evidence for the existence of a clique. Identifying cliques becomes an algorithmic task. Note that, as we will see below, even if we knew that there is a clique of a certain size in a network, we would not be able to locate it in reasonable time. Maximal cliques do always exist in a graph. In fact, there are many of them and they tend to overlap, i.e., in general it can be the case that maximal cliques U1 and U2 exist satisfying U1 = U2 and U1 U2 is non-empty. Another classical result due to Moon and Moser [432] gives a tight estimation of the number of maximal cliques: Theorem 6.1.3 (Moon and Moser, 1965). Every n with n vertices has at most 3 3 maximal cliques. undirected graph G

In reality, the expected enormous number of maximal cliques leads to the serious problem of how to identify the more important ones among them. There are only few algorithmic techniques available providing helpful interpretation of the

6 Local Density

115

maximal-clique collection. Prominent examples for methods are based on the co-membership matrix or the clique overlap centrality [192]. The family of all cliques of a certain graph shows some structure: 1. Cliques are closed under exclusion, i.e., if U is a clique in G and v U , then U {v} is also a clique.2 2. Cliques are nested, i.e., each clique of size n contains a clique of size n 1 (even n cliques of size n 1). Though this is an immediate consequence of the closure under exclusion, it is a property to be proved for related notions that are not closed under exclusion. Distance-based cliques. There is a number of approaches to generalize the notion of a clique that are relevant in several settings of social-network theory. We list some of them [400, 14, 429]. Let G = (V, E) be an undirected graph, let U be a vertex subset of V , and let N > 0 be any natural number. 1. U is said to be an N -clique if and only if for all u, v U , dG (u, v) N . 2. U is said to be an N -club if and only if diam(G[U ]) N . 3. U is said to be an N -clan if and only if U is a maximal N -clique and diam(G[U ]) N . N -cliques are based on non-local properties, as the distance between vertices u and v is measured with respect to graph G, and not with respect to G[U ]. An immediate consequence is that N -cliques need not be connected for N > 1. Though clubs and clans are local structures (except the maximality condition), they are of minor interest in our context, since they emphasize distances rather than density. Moreover, there has been some criticism of distance-based cliques, which was sparked o by at least two facts (cf., e.g., [514, 189]). First, in many cases real-world networks have globally a small diameter, thus, the distance is a rather coarse measure to identify meaningful network substructures. Second, distance-based cliques are in general neither closed under exclusion nor nested. 6.1.1 Computational Primitives

In many respects, cliques are simple objects, easily manageable from an algorithmic point of view. We have fast algorithms with run-time O(n + m) at hand for several computational primitives: 1. Determine if a given set U V of vertices is a clique in G. We simply test whether each pair of vertices of U is an edge in G. Note that these are up to n pairs, but even if we have much fewer edges, after testing m pairs we 2 are done in any case. 2. Determine if a given clique U V is maximal in G. We simply test whether there exists a vertex in V U which is adjacent to all vertices in U . Again, after testing m edges we are done in the worst case.
2

In graph theory, a property is called hereditary if and only if, whenever a graph satises , so does every induced subgraph. Being a clique is a hereditary property of graphs.

116

S. Kosub

Another eciently computable primitive is nding some maximal clique. For later use, we state this in a more general form. Suppose that the vertex set V of a graph G = (V, E) is ordered. We say that a set U V is lexicographically smaller than a set U V if and only if the rst vertex that is not in both U and U belongs to U . Our third primitive is the following: 3. Compute the lexicographically smallest maximal clique containing some clique U . We start with setting U := U , iterate over all v V U in increasing order, and test for each v whether U N (v); if this is the case then add vertex v to U . After completing the iteration, U is a maximal clique containing U . This works in time O(n + m). Algorithmic diculties appear only when we are interested in nding cliques of certain sizes or maximum cliques. For these problems, no algorithms with running times comparable to the one above are known (and, probably, no such algorithms exist). 6.1.2 Finding Maximum Cliques

We discuss several aspects of the maximum clique problem. Of course, it is easy to compute a clique of maximum size, if we do not care about time. The obvious approach is exhaustive search. In an exhaustive search algorithm, we simply enumerate all possible candidate sets U V and examine if U is a clique. We output the largest clique found. A simple estimation gives a worst-case upper bound O(n2 2n ) on the time complexity of the algorithm. Computational hardness. The problem arises whether we can improve the exhaustive search algorithm signicantly with respect to the amount of time. Unfortunately, this will probably not be the case. Computationally, nding a maximum clique is an inherently hard problem. We consider the corresponding decision problem: Problem: Input: Question: Clique Graph G, Parameter k Does there exist a clique of size at least k within G?

Let (G) denote the size of a maximum clique of a graph G. Note that if we have an algorithm that decides Clique in time T (n) then we are able to compute (G) in time O(T (n) log n) using binary search. The other way around, any T (n) algorithm for computing (G), gives a T (n) algorithm for deciding Clique. Thus, if we had a polynomial algorithm for Clique, we would have a polynomial algorithm for maximum-clique sizes, and vice versa. However, Clique was among the rst problems for which N P-completeness was established [345]. Theorem 6.1.4. Clique is N P-complete.

6 Local Density

117

Proof. Note that testing whether some guessed set is a clique is possible in polynomial time. This shows the containment in N P. In order to prove the N P-hardness, we describe a polynomial-time transformation of Satisfiability into Clique. Suppose we are given a Boolean formula H in conjunctive normal form consisting of m clauses C1 , . . . , Ck . For H we construct a k-partite graph GH where vertices are the literals of H labeled by their clause, and where edges connect literals that are not negations of each other. More precisely, dene GH = (VH , EH ) to be the following graph: VH =def EH =def (L, i) i {1, . . . , k} and L is a literal in clause Ci i = j and L = L

{(L, i), (L , j)}

Clearly, the graph GH can be computed in time polynomial in the size of the formula H. We show that H is satisable if and only if the graph GH contains a clique of size k. Suppose that H is satisable. Then there exists a truth assignment to variables x1 , . . . , xn such that in each clause at least one literal is true. Let L1 , . . . , Lk be such literals. Then, of course, it must hold that Li = Lj for i = j. We thus obtain that the set {(L1 , 1), . . . , (Lk , k)} is a clique of size k in GH . Suppose now that U VH is a clique of size k in graph GH . Since GH is k-partite, U contains exactly one vertex from each part of VH . By denition of set VH , we have that for all vertices (L, i) and (L , j) of U , L = L whenever i = j. Hence, we can assign truth values to variables in such a way that all literals contained in U are satised. This gives a satisfying truth assignment to formula H. So, unless P = N P, there are no algorithms with a running time polynomial in n for solving Clique with arbitrary clique size or computing the maximum clique. On the other hand, even if we have a guarantee that there is a clique of size k in graph G, then we are not able to nd it in polynomial time. Corollary 6.1.5. Unless P = N P, there is no algorithm running in polynomial time to nd a clique of size k in a graph which is guaranteed to have a clique of size k. Proof. Suppose we have an algorithm A that runs in polynomial time on each input (G, k) and outputs a clique of size k, if it exists, and behaves in an arbitrary way in the other cases. A can be easily modied into an algorithm A that decides Clique in polynomial time. On input (G, k), run algorithm A, if A produces no output, then reject the instance. If A outputs a set U , then test whether U is a clique. If so, accept, otherwise reject. This procedure is certainly polynomial time. Note that the hardness of nding the hidden clique does not depend on the size of the clique. Even very large hidden cliques (of size (1 )n for > 0) cannot be found unless P = N P (see, e.g., [308, 37]). The situation becomes slightly better if we consider randomly chosen graphs, i.e., graphs where each edge appears

118

S. Kosub

with probability 1 . Suppose we additionally place at random a clique of size k 2 in such a random graph size n. How fast can we nd this clique? It has been of observed that, if k = ( n log n), then almost surely the k vertices with highest degree form the clique [374]. This gives a trivial O((n + m) log n) algorithm (which can be improved to an O(n + m) algorithm with a technique discussed in Theorem 6.2.7). For k = ( n), algorithms based on spectral techniques have been proven to nd hidden cliques of size k in polynomial time [22] (even in some weaker random graph models [202]). However, many natural algorithmic techniques do not achieve the goal of nding hidden cliques of size k = o( n) [328]. Better exponential algorithms. Even though we will probably never have a polynomial-time algorithm for nding maximum cliques, we can try to design fast, super-polynomial algorithms. Exhaustive search gives the upper bound O(n2 2n ), or O (2n ) when omitting polynomial factors. Our goal is to design algorithms having running times O ( n ) with as small as possible. The following theorem that can be found in [590] shows that we can do better than exhaustive search. Theorem 6.1.6. There exists an algorithm for computing a maximum clique in time O (1.3803n ). Sketch of Proof. We use a backtracking scheme with pruning of the recursion tree. Let G be a graph having n vertices and m edges. Let v V be any vertex of minimum degree. If (G) n 3 then the graph misses collections of pairwise disjoint cycles and paths, for being a complete graph. In this case, it is fairly easy to compute a maximum clique in O(n + m).3 Assume that there is a vertex v with degree dG (v) n 4. Every maximum clique either contains v or not. Corresponding to these two cases, a maximum clique of G is either {v} combined with a maximum clique of the induced subgraph G[N (v)] or a maximum clique of the induced subgraph G[V {v}]. We recursively compute maximum cliques in both subgraphs and derive from them a solution for G (breaking ties arbitrarily). The worst-case time T (n) essentially depends on the following recursive inequality: T (n) T (n 4) + T (n 1) + c (n + m) for some c > 0

Using standard techniques based on generating functions, we calculate that T (n) is within a polynomial factor of n where 1.3803 is the largest real zero of the polynomial 4 3 1.
3

It might be easier to think of independent sets rather than cliques. An independent set in a graph G is a set U of vertices such that G[U ] has no edges. A clique in graph G corresponds to an independent set in graph G, where in G exactly those vertices are adjacent that are not adjacent in G. Independent sets are a little bit easier to handle, since we do not have to reason about edges that are not in the graph. In fact, many algorithms in the literature are described for independent sets.

6 Local Density

119

The intuitive algorithm in the theorem captures the essence of a series of fast exponential algorithms for the maximum clique problem. It started with an O (1.286n) algorithm [543] that follows essentially the ideas of the algorithm above. This algorithm has been subsequently improved to O (1.2599n ) [545], by using a smart and tedious case analysis of the neighborhood around a lowdegree vertex. The running time of the algorithm has been further improved to O (1.2346n) [330], and, using combinatorial arguments on connected regular graphs, to O (1.2108n) [495]. Unfortunately, the latter algorithm needs exponential space. This drawback can be avoided: there is a polynomial-space algorithm with a slightly weaker O (1.2227n) time complexity [54]. A non-trivial lower bound on the basis of the exponential is still unknown (even under some complexity-theoretic assumptions). 6.1.3 Approximating Maximum Cliques

Since we are apparently not able to compute a maximum clique in moderate time, we could ask up to what size we can recognize cliques in justiable time. Recall that (G) denotes the size of the largest clique in G. We say that an algorithm approximates (G) within factor f (n) if and only if the algorithm produces, on input G, a clique U in G such that (G) f (n) |U |. Note that, since a maximum clique consists of at most n vertices, we can trivially approximate maximum clique within factor O(n), simply by outputting some edge, if there is one in the graph. With a lot of work and combinatorial arguments, we arrive at the next theorem [79], which is unfortunateley not very much better than the trivial ratio. Theorem 6.1.7. There exists a polynomial-time algorithm whose output, for n graph G with n vertices, is a clique of size within factor O (log n)2 of (G). The approximation ratio stated in the theorem is the best known. The following celebrated result [287] indicates that in fact, there is not much space for improving over that ratio. Theorem 6.1.8. Unless N P = ZPP,4 there exists no polynomial-time algorithm whose output for a graph G with n vertices is a clique of size within factor n1 of (G) for any > 0. The complexity-theoretic assumption used in the theorem is almost as strong as P = N P. The inapproximability result has been strengthened to subconstant values of , rst to O log1log n [177] and further to O (log1n) [353] for some > 0. These results are based on much stronger complexity assumptions essentially, that no N P-complete problem can be solved by randomized algorithms O(1) with quasi-polynomial running time, i.e., in time 2(log n) . Note that the ratio
4

ZPP is the class of all problems that can be solved with randomized algorithms running in expected polynomial time while making no errors. Such algorithms are also known as (polynomial-time) Las Vegas algorithms.

120
n (log n)2

S. Kosub

is expressible as log log n in terms of . The gap between the lower log n bound and the upper bound for approximability is thus pretty close. Also many heuristic techniques for nding maximum cliques have been proposed. They often show reasonable behavior, but of course, they cannot improve over the theoretical inapproximability ratio. An extensive discussion of heuristics for nding maximum cliques can be found in [70]. In the random graph model, we known that, with high probability, (G) is either (2 + o(1)) log n rounded up or rounded down, for a random graph of size n (see, e.g., [24]). There are several polynomial-time algorithms producing cliques of size (1+o(1)) log n, i.e., they achieve an approximation ratio of roughly two [263]. However, it is conjectured that there is no polynomial-time algorithm outputting a clique of size at least (1 + ) log n for any > 0 [328, 347]. 6.1.4 Finding Fixed-Size Cliques

In many cases, it might be appropriate to search only for cliques of bounded sizes. Technically that is, we consider the clique size not as part of the input. For instance, exhaustive search has running time (nk ) when the clique size k is xed. A nice trick helps us to obtain an algorithm for detecting cliques of size three (triangles) faster than O(n3 ). The idea to the algorithm in the following theorem can be found in [321]. Theorem 6.1.9. There exists an algorithm for testing a graph for triangles that runs in time O(n2.376 ). Proof. Let G be any graph with n vertices. Let A(G) denote the adjacency matrix of G, i.e., entry aij of A(G) is one if vertices vi and vi are adjacent, and zero otherwise. Consider the matrix A(G)2 = A(G) A(G) where is the usual matrix multiplication. The entry bij of the matrix A(G)2 is exactly the number of walks of length two between vi and vj . Suppose there exists an entry bij 1. That is, there is at least one vertex u V dierent to vi and vj which is adjacent to both vi and vj . If the graph G has an edge {vi , vj }, then we know that G contains the triangle {vi , vj , u}. Thus, an algorithm for triangle-testing simply computes A(G)2 and checks whether there exists an edge {vi , vj } for some nonzero entry bij in A(G)2 . Since fast square matrix multiplication can be done in time O(n ) where < 2.376 [132], the algorithm runs in time O(n2.376 ). Note that for sparse graphs there is an even faster algorithm running in time 2 O(m +1 ) = O(m1.41 ) for nding triangles which makes use of the same technique [26] (see also Section 11.5). Once we have reached this point, we would like to apply the matrixmultiplication technique to come up with algorithms for clique size larger than three as well. However, the direct argument does not work for some reasons. For instance, there exists always a walk of length three between adjacent vertices. This makes the matrix A(G)3 and all higher powers ambiguous. We need a more sophisticated approach [174, 440].

6 Local Density

121

Theorem 6.1.10. For every k 3 there exists an algorithm for nding a clique of size k in a graph with n vertices that runs in time O(n(k) ) where (k) = ( k/3 , (k 1)/3 , k/3 ) and multiplying an nr ns -matrix with an ns nt matrix can be done in time O(n(r,s,t) ). Proof. Let k1 denote k/3 , let k2 denote (k 1)/3 , and let k3 denote the value k/3 . Note that k = k1 +k2 +k3 . Let G be any graph with n vertices and m edges. We rst construct a tripartite auxiliary graph G as follows: the vertex set V is 1 , V2 , and V3 where Vi consists of all cliques of size ki in G. divided into three sets V Dene two vertices U Vi and U Vj to be adjacent in G if and only if i = j and U U is a clique of size ki +kj in G. The algorithm now tests the auxiliary graph G for triangles. If there is such a triangle {U1 , U2 , U3 }, then the construction of G implies that U1 U2 U3 is a clique of size k in G. Testing the graph G for triangles can be done by matrix multiplication as described in Theorem 6.1.9. However, we now have to multiply an nk1 nk2 adjacency matrix, representing edges between V1 and V2 , with an nk2 nk3 adjacency matrix, representing edges 2 and V3 . This step can be done in time O(n(k) ). Computing the between V 2k three matrices needs in the worst case O(nmax{k1 +k2 ,k1 +k3 ,k2 +k3 } ) = O(n 3 ), which is asymptotically dominated by the time for the fast rectangular matrix multiplication [318]. We give an impression of the algorithmic gain of using matrix multiplication (see, e.g., [260]). Clique size 3 4 5 6 7 8 Exhaustive search O(n3 ) O(n4 ) O(n5 ) O(n6 ) O(n7 ) O(n8 ) Matrix multiplication O(n2.376 ) O(n3.376 ) O(n4.220 ) O(n4.751 ) O(n5.751 ) O(n6.595 )

The theorem has a nice application to the membership counting problem for cliques of xed size. The following result is due to [260]. Theorem 6.1.11. For every k 3, there exists an algorithm that counts the number of cliques of size k to which each vertex of a graph on n vertices belongs, in time O(n(k) ) where (k) is the same function as in Theorem 6.1.10. Proof. The theorem is based on the observation that for the case k = 3 (see Theorem 6.1.9), it is not only easy to check whether two vertices vi and vj belong to some triangle in G, but also to compute in how many triangles they lie: if the edge {vi , vj } exists in G, then the number is just the entry bij in the square of the adjacency matrix A(G). In general, we apply this observation to the auxiliary graph G. For any vertex v V , let Ck (v) denote the number of dierent cliques of size k in G in which v is contained. Similarly, let C3 (U ) belongs. Notice that U is a denote the number of triangles to which node U of G clique in G of size smaller than k. Clearly, cliques of G of size k may have many

122

S. Kosub

representations in graph G. The exact number is the number of partitionings of k a set of cardinality k into sets of cardinalities k1 , k2 , and k3 , i.e., k1 ,k2 ,k3 where k1 , k2 , and k3 are dened as in the proof of Theorem 6.1.10. Without loss of generality, let k1 be the minimum of these three parameters. Let U(v) be the set of all cliques U of size k1 in G such that v U . We then obtain the following equation: C3 (U ) =
UU (v)

(k 1) (k1 1), k2 , k3

Ck (v)

(6.1)

Clearly, using Theorem 6.1.10, the left-hand side of this equation can be computed in time O(n(k) ) (rst, compute the matrices and second, search entries for all U containing v). We now easily calculate Ck (v) from Equation 6.1. A recent study of the corresponding decremental problem [260], i.e., the scenario where starting from a given graph vertices and edges can be removed, has shown that we can save roughly n0.8 time compared to computing the number of size-k cliques to which the vertices belong each time from the scratch. For example, the problem of counting triangles in a decremental setting now takes O(n1.575 ). Fixed-parameter tractability. A way to study which time bounds we might expect for xed-parameter clique problems is parameterized complexity [168]. The goal here is to gure out which input parameter makes a problem computationally hard. We say that a parameterized problem (with parameter k) is xedparameter tractable if and only if there is an algorithm for the problem that needs time polynomial in input size n, if k is xed, and which is asymptotically independent of k. More precisely, the time complexity of the algorithm has the form O(f (k) p(n)) where p is some polynomial independent of k and f is an arbitrary function independent of n. Note that the algorithm above does not satisfy such a bound. A good bound would be, e.g., O(k k n2 ). However, we are far from proving such bounds, and in fact, we should not even expect to obtain such algorithms. Let F PT denote the class of xed-parameter tractable problems. We know that parameterized Clique is complete for the class W[1], a superclass of F PT [167]. However, it is widely believed that F PT = W[1], which would imply both P = N P and Clique is not xed parameter tractable. 6.1.5 Enumerating Maximal Cliques

Enumerative algorithms for the clique problem have some tradition (cf., e.g., [70]), with probably the rst appearing already in 1957 [284]. Several other, now classical, algorithms were proposed (e.g., [473, 103]). Most recently, also algorithms for the dynamic graph setting have been investigated [534]. We are interested in having ecient algorithms for enumerating maximal cliques. There are some gradations in the meaning of ecient. Most of the interesting combinatorial problems have an exponential number of congurations; n in our case indicated by the 3 3 matching upper bound for the number of maximal cliques. A typical requirement for an enumerative algorithm to be ecient

6 Local Density

123

is polynomial total time. That is, the algorithm outputs all C possible congurations in time bounded by a polynomial in C and the input size n. Exhaustive search is not polynomial total time. In contrast, one of the classical algorithms [473] rst runs O(n2 C) steps with no output and then outputs all C maximal cliques all at once. However, an algorithm for the enumeration of all maximum cliques that runs in polynomial total time does not exist, unless P = N P [382]. We next review enumerative algorithms for maximal cliques with polynomial total time having some further desirable properties. Polynomial delay. An algorithm fullling this condition generates the congurations, one after the other in some order, in such a way that the delay until the rst output, the delay between any two consecutive congurations, and the delay until it stops after the last output is bounded by a polynomial in the input size. For maximal cliques we know such algorithms that in addition, require only linear space [553]. Theorem 6.1.12. There is an algorithm enumerating all maximal cliques of a graph with polynomial delay O(n3 ) using only O(n + m) space. Proof. We construct a binary tree with n levels and leaves only at level n. Each level is associated with a vertex, i.e., at level i we consider vertex vi . The nodes of the tree at level i are all maximal cliques of G[{v1 , . . . , vi }]. It immediately follows that the leaves are exactly the maximal cliques of G. Fix level i and maximal clique U in G[{v1 , . . . , vi }]. We want to determine the children of U at level i + 1. We have two main cases: 1. Suppose all vertices of U are adjacent to vi+1 in G. Then U {vi+1 } is maximal clique in G[{v1 , . . . , vi , vi+1 }]. Note that this is the only way to obtain a maximal clique of G[{v1 , . . . , vi , vi+1 }] that contains U . In this case U has only one child in the tree. 2. Suppose there is a vertex in U not adjacent to vi+1 in G. Here, we can obtain maximal cliques in G[{v1 , . . . , vi , vi+1 }] in two dierent ways: U itself is certainly a maximal clique, and another clique is (U N (vi+1 )) {vi+1 }, where N (vi+1 ) are all vertices of G not adjacent to vi+1 . If the latter set is a maximal clique, U would have two children. However, as the set (U N (vi+1 )) {vi+1 } is potentially a child of several sets, we dene it to be the child of the lexicographically smallest set U , if it is maximal. By this denition, we have a tree where all internal nodes have one or two children, thus a binary tree, and all leaves are at level n. Our enumerative algorithm now simply traverses the tree using a depth-rst search and outputs all leaves. All we need to be able to perform the computation, given a node U of the tree at level i, is the following: Parent(U, i): According to the denition of the tree, the parent node of U is the lexicographically smallest maximal clique in G[{v1 , . . . , vi1 }] containing the clique U {vi }. This is one of our eciently computable primitives: the set can be computed in time O(n + m).

124

S. Kosub

LeftChild(U, i): If U N (vi+1 ) (the rst case above), then the left child is U {vi+1 }. If U N (vi+1 ) (one part of the second case above), then the left child is U . Checking which case has to be applied needs O(n + m) time. RightChild(U, i): If U N (vi+1 ), then there is no right child dened.If U N (vi+1 ), then the right child of U is (U N (vi+1 )) {vi+1 } if it is a maximal clique and U = Parent((U N (vi+1 )) {vi+1 }, i + 1), otherwise the right child is not dened. Note that we only need O(n + m) processing time. The longest path between any two leaves in the tree is 2n 2 passing through 2n 1 nodes. For each node we need O(n + m) time. Since any subtree of our tree has a leaf at level n, this shows that the delay between outputs is O(n3 ). Note that the algorithm only needs to store while processing a node, the set U , the level i, and a label indicating whether it is the left or the right child. Hence, the amount of space is O(n + m). Specied order. A more dicult problem is generating maximal cliques in a specic order, such as lexicographic order. If we only insist in polynomial total time, this is obviously not a restriction, since we need only collect all outputs and sort them for outputting in lexicographic order. Considering orders is only interesting in the case of polynomial delay. Note that the DFS-based polynomialdelay algorithm in Theorem 6.1.12 does not produce its outputs in lexicographic order. Another DFS-based algorithm [395] has been proposed that produces the outputs in lexicographic order but is not polynomial delay. We rst observe that it is not obvious how to break the tradeo. Theorem 6.1.13. Deciding for any given graph G and any maximal clique U of G, whether there is a maximal clique U lexicographically larger than U , is N P-complete. The theorem is proven by a polynomial transformation from Satisfiability [334]. It has some immediate consequences, e.g., it rules out polynomial-delay algorithms with respect to inverse lexicographic order. Corollary 6.1.14. 1. Unless P = N P, there is no algorithm that generates for any given graph G and any maximal clique U in G the lexicographically next maximal clique in polynomial time. 2. Unless P = N P, there is no algorithm that generates for any given graph all maximal cliques in inverse lexicographic order with polynomial delay. It might seem surprising that algorithms exist generating all maximal cliques in lexicographic order, with polynomial delay. The idea of such an algorithm is simply that while producing the current output, we invest additional time in producing lexicographically larger maximal cliques. We store these cliques in a priority queue Q. Thus, Q contains a potentially exponential number of cliques and requires potentially exponential space. The following algorithm has been proposed in [334] and uses in a clever way the tree structure employed in Theorem 6.1.12.

6 Local Density Algorithm 9: Lexicographic enumeration of maximal cliques [334] Input: Graph G = (V, E) Output: Sequence of maximal cliques of G in lexicographic order Let U0 be the lexicographically rst maximal clique; Insert U0 into priority queue Q; while Q is not empty do U :=ExtractMin(Q); Output U ; foreach vertex vj of G not adjacent to some vertex vi U with i < j do Uj := U {v1 , . . . , vj }; if (Uj N (vj )) {vj } is a maximal clique in G[{v1 , . . . , vj }] then Let T be the lexicographically smallest maximal clique which contains (Uj N (vj )) {vj }; Insert T into Q

125

Theorem 6.1.15. Algorithm 9 enumerates all maximal cliques of a graph with n vertices in lexicographic order, and with delay O(n3 ). Proof. For the correctness of the algorithm, rst observe that the set T being inserted into Q when considering U is lexicographically greater than U . Thus, we store only sets into the queue that have to be output after U . Hence, the sequence of maximal cliques we produce is indeed lexicographically ascending. We also have to show that all maximal cliques are in the sequence. We do this by proving inductively: if U is the lexicographically rst maximal clique not yet output, then U is in Q. Base of induction: Suppose U = U0 . Then the statement is obviously true. Step of induction: Suppose U is lexicographically greater than U0 . Let j be the largest index such that Uj = U {v1 , . . . , vj } is not a maximal clique in the graph restricted to vertices v1 , . . . , vj . Such an index must exist, since otherwise we would have U = U0 . Moreover, we have that j < n, since U is a maximal clique in the whole graph G. By maximality of j, we must have vj+1 U . There exists a non-empty set S such that Uj S is a maximal clique in G[{v1 , . . . , vj }]. Again, by maximality of j, the vertex vj+1 is not adjacent to all vertices in S. We conclude that there is a maximal clique U containing Uj S but not vertex vj+1 . Note that U is lexicographically smaller than U , since they dier on set S. By induction hypothesis, U has already been output. At the time when U was output, the vertex vj+1 was found not to be adjacent to some vertex vi in U with index i < j + 1. Clearly, we have (Uj+1 N (vj+1 )) {vj+1 } = Uj+1 and Uj+1 is a maximal clique in G[{v1 , . . . , vj+1 }]. So the lexicographically rst maximal clique T containing Uj+1 was inserted into Q. Once more by maximality of j, U and T coincide on the rst j + 1 vertices. Assume that U = T . Let k be the rst index such that U and T disagree on vk . It follows that k > j + 1. Since T is lexicographically less than U , we have vk T and vk U . Hence, Uk is not a / maximal clique in G[{v1 , . . . , vk }], a contradiction to maximality of j. Therefore, U = T and so U is in Q. This proves the induction step.

126

S. Kosub

For the time bound, the costly operations are the extraction of the lexicographically smallest maximal clique from Q (which needs O(n log C)), the n computations of maximal cliques containing a given set (which takes O(n+m) for each set), and attempting to insert a maximal clique into Q (at costs O(n log C) n per clique). Since C 3 3 , the total delay is O(n3 ) in the worst case. Counting complexity. We conclude this section with some remarks on the complexity of counting the number of maximal cliques. An obvious way to count maximal cliques is to enumerate them with some of the above-mentioned algorithms and increment a counter each time a clique is output. This, however, would take exponential time. The question is whether it is possible to compute the number more directly and in time polynomial in the graph size. To study such issues the class #P has been introduced [559], which can be considered as the class of all functions counting the number of solutions of instances of N P-problems. It can be shown that counting the number of maximal cliques is #P-complete (with respect to an appropriate reducibility notion) [560]. An immediate consequence is that if there is a polynomial-time algorithm for computing the number of maximal cliques, then Clique is in P, and thus, P = N P. Note that in the case of planar, bipartite or bounded-degree graphs there are polynomial-time algorithms for counting maximal cliques [557].

6.2

Structurally Dense Groups

We review two relaxations of the clique concept based on minimal degrees [515, 514, 513]. Both relaxations are structural, as they impose universal constraints on individuals in a group. 6.2.1 Plexes

We generalize the clique concept by allowing members in a group to miss some ties with other group members, but only up to a certain number N 1. This leads to the notion of an N -plex [514, 511]. Denition 6.2.1. Let G = (V, E) be any undirected graph and let N {1, . . . , n 1} be a natural number. A subset U V is said to be an N -plex if and only if (G[U ]) |U | N . Clearly, a clique is simply a 1-plex, and an N -plex is also an (N + 1)-plex. We say that a subset U V is a maximal N -plex if and only if U is an N -plex and it is not strictly contained in any larger N -plex of G. A subset U V is a maximum N -plex if and only if U has a maximum number of vertices among all N -plexes of G. It is easily seen that any subgraph of an N -plex is also an N -plex, that is, N -plexes are closed under exclusion. Moreover, we have the following relation between the size of an N -plex and its diameter [514, 189, 431].

6 Local Density

127

Proposition 6.2.2. Let N {1, . . . , n1} be a natural number. Let G = (V, E) be any undirected graph on n vertices. 1. If V is an N -plex with N < n+2 , then diam(G) 2 and, if additionally 2 n 4, G is 2-edge-connected. 2. If V is an N -plex with N n+2 and G is connected, then diam(G) 2 2N n + 2. Proof. 1. Suppose N < n+2 . Let u, v V be vertices such that u = v. If u and 2 v are adjacent, the distance between them is one. Now, suppose u and v are not adjacent. Assume that the distance between u and v is at least three, i.e., with respect to neighborhoods it holds N (u) N (v) = . We obtain n 2 |N (u) N (v)| 2(G) 2(n N ) > 2 n n+2 2 = n 2,

a contradiction. Thus, the distance between u and v is at most two. Hence, diam(G) 2. To verify that for n 4, G is 2-edge-connected, assume to the contrary that there is a bridge, i.e., an edge e such that after removing it, G{e} consists of two connected components V1 and V2 . Obviously, every shortest path from a vertex in V1 to a vertex in V2 must use that bridge. Since diam(G) 2, one component is a singleton. This implies that the vertex in this component has degree one. However, as V is an N -plex with n 4 vertices, we obtain for the degree of this vertex n N > n (n + 2)/2 = (n 2)/2 1, a contradiction. Thus, a bridge cannot exist in G. 2. Suppose N n+2 . Let {v0 , v1 , . . . , vr } be the longest shortest path of 2 G, i.e., a path that realizes the diameter r. We may suppose that r 4. Since there is no shorter path between v0 and vr , we have that vi is not adjacent to v0 , . . . , vi2 , vi+2 , . . . , vr for all i {0, . . . , r} (where vertices with negative index do not exist). Furthermore, there cannot exist a vertex adjacent to both v0 and v3 . Thus, the following inclusion is true: {v0 } {v2 , v3 , . . . , vr } (N (v3 ) {v2 , v4 }) N (v0 ) Note that we have a disjoint union on the left-hand side. We thus obtain the inequality 1 + (r 1) + dG (v3 ) 2 N . It follows r + n N 2 N . Hence, diam(G) = r 2N n + 2. From a computational point of view, nding maximum plexes is not easier than nding maximum cliques. This is immediate when we consider the variable decision problem for plexes, where the problem instance consists of graph G, the size parameter k, and the plex parameter N . Since Clique appears as instances of the form (G, k, 1), the problem is N P-complete. We discuss the complexity of nding N -plexes of certain sizes for xed N . For any natural number N > 0, we dene the following decision problem: Problem: Input: Question: N -Plex Graph G, Parameter k Does there exist an N -plex of size at least k within G?

128

S. Kosub

As 1-Plex = Clique, and thus 1-Plex is N P-complete, it is not surprising that nding maximum N -plexes is N P-hard for all N > 0 as well. Theorem 6.2.3. N -Plex is N P-complete for all natural numbers N > 0. Proof. It suces to consider the case N > 1. There is a generic proof of the theorem which is based on the fact that being an N -plex is a hereditary graph property (see, e.g., [240]). We give a direct proof in order to demonstrate the structural similarity between cliques and plexes. We describe a polynomial transformation of Clique into N -Plex. Let (G, k) be any instance of the clique problem. We construct a new graph G in the following way: we take N 1 copies of each vertex of G, connect them to each other by an edge, and all new vertices to the vertices of G except to the original one. More specically, let G = (V , E ) be the graph dened as follows: V =def V {0, 1, . . . , N 1} E =def {(u, 0), (v, 0)} | {u, v} E

{(u, i), (v, j)} | u, v V and i, j > 0

{(u, 0), (v, i)} | u, v V with u = v and i > 0

The graph G can certainly be computed in time polynomial in the size of G. A crucial observation is that copy vertices, i.e., vertices in V {1, . . . , N 1} are adjacent to all vertices in V except one. We will show that G contains a clique of size k if and only if G contains an N -plex of size k + (N 1)n. Suppose there exists a clique U V of size exactly k in G. Let U denote the vertex set in G consisting of all original vertices of U and all copies of vertices of V , i.e., U = U {0} V {1, . . . , N 1}. Notice that U has cardinality k + (N 1)n. Each vertex with label i {1, . . . , N 1} is directly connected to each other vertex in U except one vertex with label zero, thus has degree |U | 2 = k + (N 1)n 2. Each vertex (u, 0) is adjacent to all vertices in U except (u, i) with i > 0. That is, (u, 0) has degree k + (N 1)n 1 (N 1). Hence, U is an N -plex. Suppose there is no clique of size k in G. Thus, any induced subgraph of G having k k vertices has minimal degree at most k 2. Let U V be any vertex set with k + (N 1)n vertices. Then there is another set U V on k + (N 1)n vertices such that (G [U ]) (G [U ]) and U contains all copy vertices of G , i.e., U V {1, . . . , N 1}. This follows from the fact that there is always a vertex in U0 = U (V {0}) that is not adjacent to some other vertex in U0 (otherwise U0 would induce a clique of size |U0 | k in G). Remembering the observation above, we are now allowed to recursively exchange such vertices by vertices of V {1, . . . , N 1} as long as possible, without decreasing minimum degrees. We end up with a desired set U V . Since we have no size-k clique in G, we may conclude (G [U ]) (G [U ]) k + (N 1)n 2 (N 1). Hence, there is no N -plex in G .

6 Local Density

129

6.2.2

Cores

A concept dual to plexes is that of a core. Here, we do not ask how many edges are missing in the subgraph for being complete, but we simply x a threshold in terms of a minimal degree for each member of the subgroup. One of the most important things to learn about cores is that there exist polynomial-time algorithms for nding maximum cores. Cores have been introduced in [513]. Denition 6.2.4. Let G = (V, E) be any undirected graph. A subset U V is said to be an N -core if and only if (G[U ]) N . The parameter N of an N -core is the order of the N -core. A subset U V is a maximal N -core if and only if U is an N -core and it is not strictly contained in any larger N -core of G. A subset U V is a maximum N -core if and only if U has maximum number of vertices among all N -cores of G. Maximum cores are also known as main cores. Any (N + 1)-core is an N -core and any N -core is an (n N )-plex. Moreover, if U and U are N -cores, then U U is an N -core as well. That means maximal N -cores are unique. However, N -cores are not closed under exclusion and are in general not nested. As an example, a cycle is certainly a 2-core but any proper subgraph has at least one vertex with degree less than two. N -cores need not be connected. The following proposition relates maximal connected N -cores to each other. Proposition 6.2.5. Let G = (V, E) be any undirected graph and let N > 0 be any natural number. Let U and U be maximal connected N -cores in G with U = U . Then there exists no edge between U and U in G. Proof. Assume there is an edge {u, v} with u U and v U . It follows that U U is an N -core containing both U and U . Furthermore, it is connected, since U and U are connected. Some immediate consequences of the proposition are the following: the unique maximum N -core of a graph is the union of all its maximal connected N -cores, the maximum 2-core of a connected graph is connected (notice that the internal vertices of a path have degree two), and a graph is a forest if and only if it possesses no 2-cores. The next result is an important algorithmic property of N -cores, that was exhibited in [46]. Proposition 6.2.6. Let G = (V, E) be any undirected graph and let N > 0 be any natural number. If we recursively remove all vertices with degree strictly less than N , and all edges incident with them, then the remaining set U of vertices is the maximum N -core. Proof. Clearly, U is an N -core. We have to show that it is maximum. Assume to the contrary, the N -core U obtained is not maximum. Then there exists a non-empty set T V such that U T is the maximum N -core, but vertices of T have been removed. Let t be the rst vertex of T that has been removed. At that time, the degree of t must have been strictly less than N . However, as t has

130

S. Kosub

at least N neighbors in U T and all other vertices have still been in the graph when t was removed, we have a contradiction. The procedure described in the proposition suggests an algorithm for computing N -cores. We extend the procedure for obtaining auxiliary values which provide us with complete information on the core decomposition of a network. Dene the core number of a vertex v V to be the highest order N of a maximum N -core vertex v belongs to, i.e., G (v) =def max{ N | there is an N -core U in G such that v U }. A method, according to [47], for computing all core numbers is shown in Algorithm 10. The algorithm is correct due to the following reasons: any graph G is certainly a (G)-core, and each neighbor of vertex v having lower degree than v decrements the potential core number of v. A straightforward implementation of the algorithm yields a worst-case time bound of O(mn log n) the most costly operations being sorting vertices with respect to their degree. A more clever implementation guarantees linear time [47].

Algorithm 10: Computing core numbers [47] Input: Graph G = (V, E) Output: Array G containing the core numbers of all vertices in G Compute the degrees of all vertices and store them into D; Sort V in increasing degree-order D; foreach v V in sorted order do G (v):=D[v]; foreach vertex u adjacent to v do if D[u] > D[v] then D[u] := D[u] 1; Resort V in increasing degree-order of D

Theorem 6.2.7. There is an implementation of Algorithm 10 that computes the core numbers of all vertices in a given graph G = (V, E) having n vertices and m edges in time O(n + m). Proof. To reduce the running time of the algorithm, we have to speed up the sorting operations in the algorithm. This can be achieved by two techniques. 1. Since the degree of a vertex lies in the range {0, . . . , n 1}, we do sorting using n buckets, one for each vertex degree. This gives us an O(n) time complexity for initially sorting the vertex-set array V . 2. We can save resorting entirely, by maintaining information about where in the array V , which contains the vertices in ascending order of their degree, a new region with higher degree starts. More specically, we maintain an array

6 Local Density

131

J where entry J[i] is the minimum index j such that for all r j, vertex V [r] has degree at least i. We can now replace the resort-line in Algorithm 10 by the following instructions:
if u = vertex w at position J[D[u] + 1] then swap vertices u and w in V ; Increment J[D[u] + 1]

Resorting the array V in order to maintain the increasing order of degrees now takes O(1) time. Notice that the array J can initially be computed in time O(n). For the total running time of Algorithm 10, we now obtain O(n) for initializing and sorting and O(m) for the main part of the algorithm (since each edge is handled at most twice). This proves the O(n + m) implementation. Corollary 6.2.8. For all N > 0, the maximum N -core for a graph with n vertices and m edges can be computed in time O(n + m), which is independent of N .

6.3

Statistically Dense Groups

In general, statistical measures over networks do not impose any universal structural requirements on individuals. This makes them more exible than structural measures but usually harder to analyze. We turn to statistical measures for densities of graphs. 6.3.1 Dense Subgraphs

The natural notion of density of a graph is the following. Let G = (V, E) be any undirected graph with n vertices and m edges. The density (G) of G is the ratio dened as m (G) =def n .
2

That is, the density of a graph is the percentage of the number of edges of a clique, observable in a graph. We are interested in subgraphs of certain densities. Denition 6.3.1. Let G = (V, E) be an undirected graph and let 0 1 be a real number. A subset U V is said to be an -dense subgraph if and only if (G[U ]) . In an -dense subgraph, the interpretation is that any two members share with probability (or frequency) at least a relationship with each other. It is, however, immediate that even graphs of fairly high density are allowed to have isolated vertices. A clique, as the subgraph with highest density, is a 1-dense subgraph. An N -plex has density 1 N 1 . Thus, for n approaching innity, the density of n1 an N -plex approaches one. A little bit more exactly, for all N > 0 and for all

132

S. Kosub

0 1, an N -plex of size at least N is an -dense subgraph. But evidently, 1 not every (1 N 1 )-dense subgraph (when allowing non-constant densities) is n1 N an N -plex. An N -core is an n1 -dense subgraph, which can have a density arbitrarily close to zero for large n. In general, -dense subgraphs are not closed under exclusion. However, they are nested. Proposition 6.3.2. Let 0 1 be real number. An -dense subgraph of size k in a graph G contains an -dense subgraph of size k 1 in G. Proof. Let U be any -dense subgraph of G, |U | = k. Let mU denote the number of edges in G[U ]. Let v be a vertex with minimal degree in G[U ]. Note that (G[U ]) d(G[U ]) = 2mU = (G[U ])(k 1). Consider the subset U obtained k by excluding vertex v from U . Let mU denote the number of edges of U . We have mU = mU (G[U ]) (G[U ]) k k1 (G[U ])(k 1) = (G[U ]) 2 2

Hence, (G[U ]) (G[U ]) . Thus, U is an -dense subgraph. The proposition suggests a greedy approach for obtaining -dense graphs: recursively deleting a vertex with minimal degree until an -dense subgraph remains. However, this procedure can fail drastically. We will discuss this below. Walks. The density averages over edges in subgraphs. An edge is a walk of length one. A generalization of density can involve walks of larger length. To make this more precise, we introduce some notations. Let G = (V, E) be any undirected graph with n vertices. Let be any walk-length. For a vertex v V , we dene its degree of order in G as the number of walks of length that start in v. Let dG (v) denote vs degree of order in G. We set d0 (v) = 1 for all v V . G Clearly, d1 (v) is the degree of v in G. The number of walks of length in a graph G G is denoted by W (G). We have the following relation between the degrees of higher order and the number of walks in a graph. Proposition 6.3.3. Let G = (V, E) be any undirected graph. For all r for all r {0, . . . , }, W (G) = vV dr (v) dG (v). G and

Proof. Any walk of length consists of vertices v0 , v1 , . . . , v . Fix an arbitrary r {0, . . . , }. Consider the element vr . Then the walk v0 , v1 , . . . , vr contributes to the degree of order r of vr , and the walk vr , vr+1 , . . . , v contributes to the r degree of order r of vr . Thus, there are dr (vr ) dG (vr ) walks of length G having vertex vr at position r. Summing over all possible choices of a vertex at position r shows the statement. It is clear that the maximum number of walks of length in a graph with n vertices is n(n 1) . We thus dene the density of order of a graph G as

6 Local Density

133

(G) =def

W (G) . n(n 1)

Note that 1 (G) = (G) as in W1 (G) each edge counts twice. We easily conclude the following proposition. Proposition 6.3.4. It holds numbers 2. (G)
1 (G)

for all graphs G and all natural

Proof. Let G = (V, E) be any undirected graph with n vertices. By Proposition 1 1 6.3.3, W (G) = vV d1 (v)dG (v) (n1) vV dG (v) = (n1)W 1 (G). G Now, the inequality follows easily. For a graph G = (V, E) we can dene a subset U V to be an -dense subgraph of order if and only if (G[U ]) . From the proposition above, any -dense subgraph of order is an -dense subgraph of order 1 as well. The -dense subgraphs of order 2 inherit the property of being nested from the -dense subgraphs. If we x a density and consider dense subgraphs of increasing order, then we can observe that they become more and more similar to cliques. A formal argument goes as follows. Dene the density of innite order of a graph G as (G). (G) =def lim

The density of innite order induces a discrete density function due to the following zero-one law [307]. Theorem 6.3.5. Let G = (V, E) be any undirected graph. 1. It holds that (G) is either zero or one. 2. V is a clique if and only if (G) = 1. The theorem says that the only subgroup that is -dense for some > 0 and for all orders, is a clique. In a sense, the order of a density functions allows a scaling of how important compactness of groups is in relation to density. Average degree. One can easily translate the density of a graph with n vertices into its average degree (as we did in the proof of Proposition 6.3.2): d(G) = (G)(n 1). Technically, density and average degree are interchangeable (with appropriate modications). We thus can dene dense subgraphs alternatively in terms of average degrees. Let N > 0 be any rational number. An N -dense subgraph of a graph G = (V, E) is any subset U V such that d(G[U ]) N . Clearly, an -dense subgraph (with respect to percentage densities) of size k is an (k 1)-dense subgraph (with respect to average degrees), and an N -dense N subgraph (with respect to average degrees) of size k is an k1 -dense subgraph (with respect to percentage densities). Any N -core is an N -dense subgraph. N dense subgraphs are neither closed under exclusion nor nested. This is easily seen by considering N -regular graphs (for N ). Removing some vertices decreases the average degree strictly below N . However, average degrees allow a more ne-grained analysis of network structure. Since a number of edges quadratic

134

S. Kosub

in the number of vertices is required for a graph to be denser than some given percentage threshold, small graphs are favored. Average degrees avoid this pitfall. Extremal graphs. Based upon Turns theorem (see Theorem 6.1.2), a whole new a area in graph theory has emerged which has been called extremal graph theory (see, e.g., [66]). It studies questions like the following: how many edges may a graph have such that some of a given set of subgraphs are not contained in the graph? Clearly, if we have more edges in the graph, then all these subgraphs must be contained in it. This has been applied to dense subgraphs as well. The following classical theorem due to Dirac [156] is a direct strengthening of Turns a theorem. Theorem 6.3.6 (Dirac, 1963). Let G = (V, E) be any undirected graph. If 2 m > n k2 , then G contains subgraphs of size k + r having average degree at 2 k1 r least k + r 1 k+r for all r {0, . . . , k 2} and n k + r. Notice that the case r = 0 corresponds to the existence of size-k cliques as expressed by Turns theorem. In many cases, only asymptotic estimations are a possible. For example, it can shown that, for a graph G = (V, E) on n vertices be
2

and m edges, if m = n2 dk , then G has a subgraph with k vertices and average degree d [368, 262]. It follows that to be sure that there are reasonably dense subgraphs of sizes not very small, the graph itself has to be reasonably dense. Some more results are discussed in [262]. 6.3.2 Densest Subgraphs

We review a solution for computing a densest subgraph with respect to average degrees. Let (G) be the maximum average degree of any non-empty induced subgraph of G, i.e., (G) =def max{ d(G[U ]) | U V and U = }. As in the case of N -cores, the maximal subgraph realizing (G) is uniquely determined. We consider the following problem: Problem: Input: Output: Densest Subgraph Graph G A vertex set of G that realizes (G)

This problem can be solved in polynomial time using ow techniques [477, 248, 239]; our proof is from [248]. Theorem 6.3.7. There is an algorithm for solving Densest Subgraph on 2 graphs with n vertices and m edges in time O(mn(log n)(log n )). m

6 Local Density

135

Proof. We formulate Densest Subgraph as a maximum ow problem depending on some parameter + . Let G = (V, E) be any undirected graph with n vertices and m edges. Consider a ow network consisting of graph G = (V , E ) and capacity function u : E + given as follows. Add to V a source s and a sink t; replace each edge of G (which is undirected) by two directed edges of capacity one each; connect the source to all vertices of V by an edge of capacity m; and connect each vertex v V to the sink by an edge of capacity m + dG (v). More specically, the network is dened as V =def V {s, t} E =def {(v, w) | {v, w} E} {(s, v) | v V } {(v, t) | v V } and for v, w V the capacity function u is dened as if {v, w} E 1 m if v = s u (v, w) =def m + dG (v) if w = t 0 if (v, w) E / We consider capacities of cuts in the network. Let S, T be any partitioning of V into two disjoint vertex sets with s S and t T , S+ = S {s} and T+ = T {t}. Note that S+ T+ = V . If S+ = , then the capacity of the cut is c(S, S) = m|V |. Otherwise we obtain: c(S, T ) =
vS,wT

u (v, w) u (s, w) +
wT+ vS+

u (v, t) +
vS+ ,wT+

u (v, w) dG (v) + 1
vS+ ,wT+ {v,w}E

= m|T+ | + m|S+ | + |S+ |

= m|V | + |S+ | 1 |S+ | dG (v)

1
vS+ ,wT+ {v,w}E

= m|V | + |S+ |( d(G[S+ ]))

(6.2)

It is clear from this equation that is our guess on the maximum average degree of G. We need to know how we can detect whether is too big or too small. We prove the following claim. Claim. Let S and T be sets that realize the minimum capacity cut, with respect to . Then we have the following: 1. If S+ = , then (G). 2. If S+ = , then (G).

136

S. Kosub

The claim is proven by the following arguments. 1. Suppose S+ = . Since c({s}, V {s}) = m|V | c(S, T ), we have |S+ |( d(G[S+ ])) 0. Hence, d(G[S+ ]) (G). 2. Suppose S+ = . Assume further to the contrary, that < (G). Let U V be any non-empty vertex subset satisfying d(G[U ]) = (G). By Equation 6.2, we obtain c(U {s}, U {t}) = m|V | + |U |( (G)) < m|V | = c(S, T ), a contradiction to the minimality of the cut capacity c(S, T ). Thus, (G). The claim suggests an algorithm for nding the right guess for by binary search. Notice that (G) can have only a nite number of values, i.e., (G) 2i j i {0, . . . , m} and j {1, . . . , n} .

It is easily seen that the smallest possible distance between two dierent points 1 in the set is n(n1) . A binary search procedure for nding a maximum average degree subgraph is given as Algorithm 11.

Algorithm 11: Densest subgraph by min-cut and binary search [248] Input: Graph G = (V, E)) Output: A set of k vertices of G Initialize l := 0, r := m, and U := ; 1 while r l n(n1) do l+r := 2 ; Construct ow network (V , E , u ); Find minimum cut S and T of the ow network; if S = {s} then r := else l := ; U := S {s} Return U

For a time bound, note that we execute the iteration log((m+1)n(n1)) = O(log n) times. Inside each iteration we have to run an algorithm which nds a minimum capacity cut. If we use, e.g., the push-relabel algorithm [252] for 2 max-ow computations, we can do this in time O(nm log n ) in a network with m n vertices and m edges. Out network has n + 2 vertices and 2m + 2n edges. This does not change the complexity of the max-ow algorithm asymptotically. We 2 thus obtain the overall time bound O(nm(log n)(log n )). m

6 Local Density

137

Parametric maximum ow algorithms [239, 6] have been employed to improve 2 the time bound to O(nm log n ) [239]. In [113], Densest Subgraph has been m solved by linear programming. This gives certainly a worse upper bound for the time complexity, but has some extensions to the case of directed graphs. Directed graphs. There is no obvious way to dene the notion of density in directed graphs. Since average in-degree and average out-degree in a directed graph are always equal, both measures are not sensitive to orientedness. One approach followed in the literature [342, 113] is based on considering two vertex sets S and T , which are not necessarily disjoint, to capture orientations. For any directed graph G = (V, E) and non-empty sets S, T V , let E(S, T ) denote the set of edges going from S to T , i.e., E(S, T ) = {(u, v) | u S and v T }. We dene an average degree of the pair (S, T ) in the graph as [342]: |E(S, T )| . dG (S, T ) =def |S| |T | This notion was introduced to measure the connectedness between hubs and authorities in web graphs. The set S is understood as the set of hubs, and the set T is understood as the set of authorities in the sense of [359], or fans and centers in the sense of [376]. If S = T then dG (S, T ) is precisely the average degree of G[S] (i.e., the sum of the average in-degree and the average out-degree of G[S]). The maximum average degree for a directed graph G = (V, E) is dened as (G) =def max{ dG (S, T ) | S, T V and S = , T = }. Densest Subgraph on directed graphs can be solved in polynomial time by linear programming [113]. To do so, we consider the following LP relaxations LP , where ranges over all possible ratios |S|/|T |: max (u,v)E x(u,v) s.t. x(u,v) su for all (u, v) E x(u,v) tv for all (u, v) E uV su 1 tv vV x(u,v) , su , tv 0 for all u, v V and (u, v) E It can be shown that the maximum average degree for G is the maximum of the optimal solutions for LP over all . Each linear program can be solved in polynomial time. Since there are O(n2 ) many ratios for |S|/|T | and thus for , we can now compute the maximum average degree for G (and a corresponding subgraph as well) in polynomial time by binary search. 6.3.3 Densest Subgraphs of Given Sizes

The densest subgraph of a graph is highly fragile, as a graph with some average degree need not possess a subgraph with the same average degree. We are thus

138

S. Kosub

not able to deduce easily information on the existence of subgraphs with certain average degrees and certain sizes, from a solution of Densest Subgraph. We discuss this problem independently. For an undirected graph G = (V, E) and parameter k , let (G, k) denote the maximum value of the average degrees of all induced subgraphs of G having k vertices, i.e., (G, k) =def max{ d(G[U ]) | U V and |U | = k }. The following optimization problem has been introduced in [201]: Problem: Input: Output: Dense k-Subgraph Graph G, Parameter k A vertex set of G that realizes (G, k)

In contrast to Densest Subgraph, this problem is computationally dicult. It is clear that Dense k-Subgraph is N P-hard (observe that the instance (G, k, k 1) to the corresponding decision problem means searching for a clique of size k in G). The best we may hope for is a polynomial algorithm with moderate approximation ratio. A natural approach for approximating (G, k) is based on greedy methods. An example of a greedy procedure due to [201] is given as Algorithm 12.

Algorithm 12: Greedy procedure Input: Graph G = (V, E) and even parameter k Output: A set of k vertices of G

(with |V | k)

Sort the vertices in decreasing order of their degrees; Let H be the set of k vertices of highest degree; 2 Compute NH (v) = |N (v) H| for all vertices v V H; Sort the vertices in V H in decreasing order of the NH -values; Let R be the set of k vertices of V H of highest NH -values; 2 Return H R

Theorem 6.3.8. Let G be any graph with n vertices and let k be an even natural number with k n. Let A(G, k) denote the average degree of the subgraph of G induced by the vertex set that is the output of Algorithm 12. We have (G, k) 2n A(G, k). k

Proof. For subsets U, U V , let E(U, U ) denote the set of edges consisting of one vertex of U and one vertex of U . Let mU denote the cardinality of the edge set E(G[U ]). Let dH denote the average degree of the k vertices of G with 2 highest degree with respect to G. We certainly have, dH (G, k). We obtain |E(H, V H)| = dH |H| 2mH dH k 2mH 0. 2

6 Local Density

139

By the greedy rule, at least the fraction of |R| k k = > |V H| 2n k 2n of these edges has been selected to be in G[H R]. Hence, the total number of edges in G[H R] is at least dH k 2mH 2 dH k 2 k + mH . 2n 4n

This proves the inequality for the average degree. The greedy procedure is the better the larger k is in relation to n. It is an appropriate choice if we want to nd large dense regions in a graph. However, for very small parameters, e.g., for k = O(1), it is almost as bad as any trivial procedure. An approximation ratio O( n ) has been obtained by several other approximation k methods, e.g., by greedy methods based on recursively deleting vertices of minimal degree [38] or by semidenite programming [204, 531]. However, to overcome the connection between n and k, we need complementary algorithms that work well on smaller values of k. In the light of the following theorem [201], this seems 2 possible for up to k = O(n 3 ). Theorem 6.3.9. Dense k-Subgraph can be approximated in polynomial time 1 within ratio O(n 3 ) for some > 0. No better bound for the general problem is known. In special graph classes, however, approximation can be done within better ratio. For instance, on families of dense graphs, i.e., graphs with (n2 ) edges, there exist polynomial-time approximation algorithms with ratio arbitrary close to one [35, 137]. A drawback here is that most of the social networks are sparse, not dense. As to lower bounds on the approximation ratio, it has recently been proven that an approximation ratio of 1 + for all > 0 cannot be achieved unless all N P problems can be simulated by randomized algorithms with double-sided error and sub-exponential running time (more specically, in time O(2n ) for all > 0)[354]. Moreover, it is even conjectured that there is no polynomial-time algorithm with approximation ratio O(n ) for all > 0 [201]. 6.3.4 Parameterized Density

As we have argued, the decision version of Dense k-Subgraph is N P-complete. In contrast to this variable decision problem (note that the density parameter is part of the input), we are now interested in studying the xed-parameter version. A function : + is a density threshold if and only if is computable in polynomial time and (k) k 1 for all k . For any density threshold , a -dense subgraph of a graph G = (V, E) is any subset U V such that d(G[U ]) (|U |). We consider the following problem:

140

S. Kosub

Problem: Input: Question:

-Dense Subgraph Graph G, Parameter k Does there exist -dense subgraph of size k within G?

Clearly, on the one hand, if we choose (k) = k 1 for all k , then we obtain -Dense Subgraph = Clique, and thus an N P-complete problem. On the other hand, if we choose (k) = 0, then any choice of k vertices induces a -dense subgraph and thus -Dense Subgraph is solvable in polynomial time. The question is: which choices of do still admit polynomial-time algorithms and for which does the problem become N P-complete? This problem has been studied by several authors [204, 37, 308]. The following theorem due to [308] gives a sharp boundary, which also shows that a complexity jump appears very early. Theorem 6.3.10. Let be any density threshold.
1 1. If = 2 + O k , then -Dense Subgraph is solvable in polynomial time. 1 2. If = 2 + k1 for some > 0, then -Dense Subgraph is N Pcomplete.

A direct application of the theorem gives the following result for the case of constant density functions. Corollary 6.3.11. Finding a k-vertex subgraph with average degree at least two can be done in polynomial time. However, there is no algorithm for nding a kvertex subgraph with average degree at least 2 + for any > 0, unless P = N P. This result should be contrasted with the corresponding result for N -cores, where detecting N -cores of size k can be done in linear time in the graph size, even for all N > 0. This demonstrates a drastic computational dierence between statistical and structural density. Results similar to Theorem 6.3.10 have been proven for the case of special network classes with real-world characteristics, in particular, for power-law graphs and general sparse graphs [306].

6.4

Chapter Notes

In this chapter, we studied computational aspects of notions of local densities, i.e., density notions dened over induced subgraphs only, consequently suppressing network structure outside a subgroup. We considered structural (N -plexes, N -cores) and statistical relaxations (-dense subgraphs) of the clique concept, which is the perfectly cohesive subgroup. Although many algorithmic problems for these notions are computationally hard, i.e., we do not know polynomial algorithms for solving them, there are several cases where fast algorithms exist producing desirable information on the density-based cohesive structure of a network, e.g., the number of small cliques in graphs, core numbers, or the maximum average degree reachable by a subgroup in a directed and undirected network.

6 Local Density

141

An observation coming up from the presented results is that there is a seemingly hard tradeo between mathematical soundness and meaningfulness of these notions and their algorithmic tractability. This is evident from the following table summarizing properties of our main notions:

subgroup clique N -plex (for N ) N -core (for N ) -dense subgraph (for [0, 1])

closed under exclusion + +

nested + + +

tractable +

Here, we see that nestedness, as a meaningful structure inside a group, excludes fast algorithms for computing subgroups of certain sizes. This exclusion is also inherited by some further relaxations. However, we have no rigorous proof for this observation in case of general locally denable subgroups. On the other hand, a similar relation is provably true for closure under exclusion and eciently detecting subgroups of a given size: we cannot achieve both with an appropriate notion of density (see, e.g., [240, GT21,GT22]). We conclude this chapter with a brief discussion of a selection of non-local concepts of cohesive subgroups that have attracted interest in social network analysis. Since non-locality emphasizes the importance for a cohesive subgroup to be separated from the remaining network, such notions play an important role in models for core/periphery structures [84, 193]. An extensive study of non-local density notions and their applications to network decomposition problems can be found in Chapter 8 and Chapter 10. LS sets (Luccio-Sami sets). The notion of an LS set has been introduced in [399, 381]. An LS set can be seen as a network region where internal ties are more signicant than external ties. More specically, for a graph G = (V, E) a vertex subset U V is said to be an LS set if and only if for all proper, non-empty subsets U U , we have |E(U , V U )| > |E(U, V U )|. Trivially, V is an LS set. Also the singleton sets {v} are LS sets in G for each v V . LS sets have some nice structural properties. For instance, they do not non-trivially overlap [399, 381], i.e., if U1 and U2 are LS sets such that U1 U2 = , then either U1 U2 or U2 U1 . Moreover, LS sets are rather dense: the minimum degree of a non-trivial LS set is at least half of the number of outgoing edges [512]. Note that the structural strength of LS sets depends heavily on the universal requirement that all proper subsets share more ties with the network outside than the set U does (see [512] for a discussion of this point). Some relaxations of LS sets can be found in [86].

142

S. Kosub

Lambda sets. A notion closely related to LS sets is that of a lambda set. Let G = (V, E) be any undirected graph. For vertices u, v V , let (u, v) denote the number of edge-disjoint paths between u and v in G, i.e., (u, v) measures the edge connectivity of u and v in G. A subset U V is said to be a lambda set if and only if max (u, v). min (u, v) >
u,vU uU,vV U

In a lambda set, the members have more edge-disjoint paths connecting them to each other than to non-members. Each LS set is a lambda set [512, 86]. Lambda sets do not directly measure the density of a subset. However, they have some importance as they allow a polynomial-time algorithm for computing them [86]. The algorithm essentially consists of two parts, namely computing the edgeconnectivity matrix for the vertex set V (which can be done by ow algorithms in time O(n4 ) [258]) and based on this matrix, grouping vertices together in a level-wise manner, i.e., vertices u and v belong to the same lambda set (at level N ) if and only if (u, v) N . The algorithm can also be easily extended to compute LS sets. Normal sets. In [285], a normality predicate for network subgroups has been dened in a statistical way over random walks on graphs. One of the most important reasons for considering random walks is that typically the resulting algorithms are simple, fast, and general. A random walk is a stochastic process by which we go over a graph by selecting the next vertex to visit at random among all neighbors of the current vertex. We can use random walks to capture a notion of cohesiveness quality of a subgroup. The intuition is that a group is the more cohesive the higher the probability is that a random walk originating at some group member does not leave the group. Let G = (V, E) be any undirected graph. For d and + , a subset U V is said to be (d, )-normal if and only if for all vertices u, v U such that dG (u, v) d, the probability that a random walk starting at u will reach v before visiting any vertex w V U , is at least . Though this notion is rather intuitive, we do not know how to compute normal sets or decomposing a network into normal sets. Instead, some heuristic algorithms, running in linear time (at least on graphs with bounded degree), have been developed producing decompositions in the spirit of normality [285].