Transitive Closure and Metric Inequality of Weighted Graphs ...

Transitive Closure and Metric Inequality of Weighted Graphs
– Detecting Protein Interaction Modules Using Cliques
Chris Ding, Xiaofeng He, Hui Xiong, Hanchuan Peng, Stephen R. Holbrook
Lawrence Berkeley National Laboratory
University of California, Berkeley, CA 94720.
June 2, 2006. Updated October 1, 2007
Abstract
We study transitivity properties of edge weights in complex networks. We show that enforcing
transitivity in affinity graphs leads to maximal transitive affinities which satisfy transitivity inequalities
equivalent to ultra-metric and harmonic triangle inequalities. This can be used to define transitive
closure on weighted graphs, and can be computed efficiently using a modified Floyd-Warshall algorithm.
From this, we extend the clique concept from unweighted graph to weighted graph. These new concepts
and theorems are extended to dissimilarity graphs. We outline several applications and present results
of detecting protein functional modules in a protein interaction network.
Keywords: transitive closure, ultrametric, triangle inequality, weighted graph, protein interaction
1
Introduction
Complex network studies include the internet and the Web, social networks, biological networks, etc. Much
progress has been made in degree distribution, network topology, growth models, small-world effect, etc.
In this paper, we study transitivity properties of edge weights, reflecting affinity between two proteins,
relatedness between two persons or similarity between two webpages. Generally speaking, these complex
networks exhibit some level of transitivity. For example, for 3 persons A, B, C, if A is related to (a friend
of) B and B is related to C, A is likely to be related to C, at least in comparison with two randomly
selected persons. In the protein interaction network, if protein pi interacts with protein pj and protein
pj interacts with protein pk, it is likely that protein pi also interacts with protein pk. Another way to
characterize the same feature is to say that the average clustering coefficient of the network is large (in the
language of small world(Watts and Strogatz, 1998)).
Beyond this general understanding, not many studies on network transitivity exist so far. In the social
network field, there are some studies focusing on statistical evidence of this being true (Wasserman and
Faust, 1994). We wish to push this further and in a somewhat different direction. We ask: Over a large
number of different networks, what kind of transitivity we should expect? What are the consequences of
transitivity of network affinity (edge weights)?
At present, most network models use unweighted graphs (edge weights are either 1 or 0). This is a
simplification convenient for understanding large scale properties. A detailed study of transitivity requires
a “quantitative” analysis, i.e., the edge weights in the network are more realistically assigned on a gradual
scale. For example, in a protein interaction network, the weight (the interaction strength) should be the
1

---

probability that two proteins have a synergistic interaction. In a social network data (Freeman’s electronic
information exchange system data(Wasserman and Faust, 1994)), the relationship between two persons
has 5 scales: (1) don’t know each other; (2) have heard of the other, but never met; (3) have met ; (4) are
friends; (5) are close friends. Therefore, we focus on weighted graphs.
We approach the transitivity problem by seeking maximum mathematical consistency, and relate it to
the well-known properties of metric distances, such as the triangle inequality and the ultra-metric inequality.
Note that we are not “asserting” that complex networks “must” follow mathematical consistency. Our goal
is to see how far we can go by assuming mathematical consistency.
In §2 we introduce a new concept of transitive affinity and discuss its properties. We show that transitive
affinity satisfies an inequality which is shown to be equivalent to the ultra-metric inequality of a distance
metric. Through this, we introduce the concept of transitive closure of a weighted graph. An efficent
algorithm is also presented. In §3- §4, the transitive closure on affinity graphs is extended to dissimilarity
graphs and to situations where triangle inequalities hold.
In §5, we outline several applications of transitive closure of weighted graphs. In §6, we extend the
clique concept from unweighted graph to weighted graph. In §7 - §8, we present results of detecting protein
functional modules from protein interaction networks. A preliminary version of this work has appeared in
Ding et al. (2005).
2
Transitive affinity of a weighted affinity graph
2.1
Transitivity and associativity
We study transitive properties of affinity graphs where the edge weights measure pairwise affinities between
nodes. We use the protein interaction as example.
Suppose protein p1 strongly interacts with p2, say w12 = 0.7. Suppose protein p2 strongly interacts
with p3, say w23 = 0.9. Given these, there is a reasonable probability that protein p1 also interacts with
p3, i.e., there is a nonzero transitive affinity between p1 and p3. There are three probable quantitative ways
to characterize the transitivity:
Tmax(w12, w23) = max(w12, w23) = 0.9,
(1)
Tavg(w12, w23) = (w12 + w23)/2 = 0.8,
(2)
Tmin(w12, w23) = min(w12, w23) = 0.7.
(3)
Let P13 = (1, 2, 3) be the path connecting p1 to p3. We say that T(w12, w23) = T(P13) = T(1, 2, 3) is the
transitive affinity along path P13, which is a 2-hop path (passing through 2 edges). The question is: among
the three possible choices, which one best captures the transitivity and satisfies many other consitency
principles?
Suppose protein p3 interacts with another protein p4. Thus a nonzero transitive affinity T(P14) =
T(1, 2, 3, 4) exists between p1 and p4. For the transitive affinity to be consistent along a path of (1, 2, 3, 4),
we require it have the associativity:
T(T(w12, w23), w34) = T(w12, T(w23, w34))
(4)
2

---

With this associativity, T(w12, w23, w34) is uniquely defined and is denoted as T(P14). One can easily
extend this to longer paths. It is clear that Tavg does not satisfy associativity; this rules out Tavg. Both
Tmax and Tmin satisfy associativity. In general, transitivity is regulated by the weakest link on the path.
Thus we choose T = Tmin. In the rest of this paper, we study the transitivity associated with Tmin. The
transitive affinity on the path Pij = (i, k1, · · · , km, j) is therefore
T(Pij ) = min (wi,k , w
, · · · , w
, w
1
k1,k2
km
k
−1 ,km
m ,j ).
(5)
2.2
Maximal transitive affinity
Transitive affinity is defined on a specific path. In general, fixing nodes i, j, transitive affinities on different
paths connecting i, j are different. For this reason, we define maximal transitive affinity between i, j as
hij = max T(Pij ),
(6)
Pij
where Pij is any possible path between i, j. Given a graph, the maximal transitive affinity between any
pair of vertices is uniquely defined. We can show that
hij ≥ wij, ∀i, j.
(7)
This implies the maximal transitive affinities bring nodes of the network more close than the original affinity
metric. Furthermore, we can prove that
Theorem 1. For any weighted graph, the maximal transitive affinity between any pair of vertices satisfies
the following transitive affinity inequality relationship
hij ≥ min(hik, hkj) ∀i, j, k.
(8)
Proof. Let(Pik, Pkj) be a path starting at i, going through k, and ending at j. Pij is a path starting at i
and ending at j. Clearly {(Pik, Pkj)} is a subset of {Pij}. Thus,
hij
= max min W (Pij)
(9)
Pij
≥
max min W (Pik, Pkj)
(10)
(Pik,Pkj )
=
max min min W (Pik) , min W (Pkj)
(11)
(Pik,Pkj )
= min max(min W (Pik) ), max(min W (Pkj) )
(12)
Pik
Pkj
= min(hik, hkj).
(13)
⊓
–
2.3
Metric inequality
Here we show that the transitive affinity inequality is identical to the ultra-metric of a distance metric,
and therefore, a general principle.
3

---

Recall the definition of the metric space. A function d(xi, xj) = dij on all pairs of objects in the space,
i.e., pairwise dissimilarities, is a metric, if (m1) nonnegativity: dij ≥ 0 ∀i, j. (m2) identity: dij = 0 if xi =
xj. (m3) symmetry: dij = dji. (m4) triangle inequality
dij ≤ dik + dkj.
(14)
A metric function preserves the important notion of distance. Metric space has a large number of properties
and is useful for many problems. A special case of metric space is ultra-metric space, where the triangle
inequality is replaced by a stronger ultra-metric inequality
dij ≤ max(dik, dkj).
(15)
A dissimilarity function satisfying the ultra-metric inequality also satisfies the triangle inequality; however,
not all metric functions satisfy ultra-metric inequality.
First, we note that similarity is a decreasing function of distance: the more similar two objects are, the
smaller their distance is. Thus sij = f (dij), where f (·) is a monotonic decreasing function (more precisely,
a nonincreasing function).
Theorem 2. The distance-based ultra-metric inequality is identical to the similarity-based transitive
affinity inequality, assuming that sij = f (dij) is a nonincreasing function.
Proof. By construction, sij = f (dij) ≥ f ( max(dik, dkj) ) = min(f (dik), f (dkj))
⊓
–
The ultra-metric inequality Eq.(15)] can be viewed as a general principle (or a highly desirable property
for distance functions) from the aximatic point of view, similar to the triangle inequality. Therefore, we
may consider the transitive affinity inequality of Eq.(8) as a general principle that affinity functions should
obey.
2.4
Transitive closure of a weighted graph
If we repeat the same line of discussions of transitive affinity in §2.1 - §2.2 on an unweighted graph, it is
clear that the maximal transitive affinity hij will be 1 between any two nodes in a connected component.
This process is very similar to the concept of transitive closure of a directed unweighted graph. Thus the
transitive closure of an undirected unweighted graph is the complete graph on the nodes of any connected
component.
Now we further extend this concept to an undirected weighted graph with weight {wij}. We replace
the original weight wij by the maximal transitive affinity hij. The new graph weights are thus consistent
with the idea of transitivity of affinity relationship, because it satisfies the transitive affinity inequality. We
therefore have
Definition 1. The transitive closure of weighted graph G is formed by their maximal transitive affinity
hij.
Remark. This definition can be extended to the transitive closure of a weighted directed graph, by gener-
alizing the maximal transitive affinity hij to directed graphs in a straightfoward manner. For unweighted
graphs, this definition reduces to the standard definition of transitive closure.
4

---

2.5
Computing transitive closure of a weighted graph
Computing maximal transitive affinity hij by its original definition Eq.(6) is farily complicated. Instead,
we compute them using the dynamical programming approach similar to the Bellman-Ford algorithm for
computing the shortest path problem Cormen et al. (1998). In Bellman-Ford algorithm, the deviation from
the sub-optimal condition on each pair of nodes are iteratively tightened (relaxed in the original word).
Bellman-Ford algorithm is used to compute the shortest paths from a fixed node to the rest of the
graph nodes. Generalizing Bellman-Ford algorithm to compute shortest path between all pair of nodes is
the Floyd-Warshall algorithm which can be viewed as iteratively tightening the deviation from the sub-
optimal condition. In shortest path problem, the sub-optimal condition is the triangle inequality Eq.(14).
Coming back to our minimal transitive affinity hij, the sub-optimal condition is the transitive affinity
inequality Eq.(8) for which hij must satisfies.
Theorem 3. The transitive closure of weighted graph G can be equivalently computed by iteratively
increasing edge weights such that the transitive affinity inequality is satisfied.
This theorem is the consequence of Theorems 4A and 4B below.
Theorem 4A. Suppose the edge weights of given graph satisfy the transitive affinity inequality. The
transitive affinities as defined in Eq.(6) are equal to edge weights: hij = wij. (This theorem plays the role
of Lemma 24.14 convergence property in Cormen et al. (1998)).
Proof. We first show that for 2-hop paths, maximal transitive weight is equal to the edge weight. Fixing
i, j, we consider a 2-hop path i − k − j. Since weights satistify transitive affinity inequality, wij must be
larger or equal to 2-hop transitive weight t(Pikj ) for any k. Thus the 2-hop maximal transitive weight
between i, j. must be wij. This is valid for all i, j pairs.
Now consider 3-hop paths between i, j. Consider a 3-hop path i − k − l − j. Since for 2-hop paths,
maximal transitive weight is equal to the edge weight, we can replace i − k − l by i − l, or replace k − l − j
by k − j when computing maximal transitive weight. Thus we need consider only 2-hop paths i − l − j and
i − k − j. Apply the 2-hop path equivalence property, these two paths have the same maximal transitive
weight as path i − j. Thus the maximal transitive weight for the path i − k − l − j is wij. This is valid for
all possible i, k, l, j.
The proof for 4-hop paths, 5-hop paths, etc. are the same.
⊓
–
Theorem 4B. Given a pair of nodes (i, j). Let (i, k1, k2, · · · , km, j) be the path with the eventual minimal
transitive affinity hij. After successive relaxation (tightening) of edges (i, k1), (k1, k2), · · · , (km−1, km), (km, j)
in order, the transitive affinity hij achieves the final optimal minimal transitive affinity. This holds no mat-
ter what other edges relax occur. (This is Lemma 24.15, path relaxation property in Cormen et al. (1998)).
Proof. Given the optimal path, the length-2 transitive affinity is easily determined and this is obviously the
optimal solution. The length-3 transitive affinity is easily determined based on the the length-2 transitive
affinity and the weight of the 3rd edge. This is extended to the last edge on the path.
⊓
–
Theorems 4A and 4B are the basis for the algorithm to compute minimal transitive affinity.
5

---

2.6
Modified Floyd-Warshall algorithm
Using Theorems 4A and 4B, we see that for computation of maximal transitive affinities on multi-hop
paths, it is sufficient to consider 2-hop paths only and simultaneously tightening all hij’s. Eventually hij
converges to the optimal solution. This 2-hop path (or triangle) only property is crucial to for an efficient
algorithm implementation.
Since to verify whether a given graph weights satisfy transitive closure, we need to go through all
possible triangles n = n(n − 1)(n − 2)/3! = O(n3) to check the transitive affinity inequality. This is the
3
minimal computational cost.
Implementation of Theorem 4A and 4B can be shown to be a slight modification of the Floyd-Warshall
algorithm for all-pair shortest paths in O(n3). Since O(n3) is the the minimal computational cost, the
Floyd-Warshall algorithm is optimally efficient.
Given input W , the weight matrix of a network, the algorithm computes the maximal transitive affinity
as the following:
Floyd-Warshall to compute transitive closure of graph with weights W .
1
H = W
2
for k = 1 to N
3
do for i = 1 to N
4
do for j = 1 to N
5
hij = max(hij, min(hik, hkj))
6
return H
The modification from standard the Floyd-Warshall algorithm is on Line 5, updating hij, which uses Eq.(8)
for satisfying the transitive affinity inequality.
The correctness of this algorithms is proved by the following. (1) From Theorem 4B, for any optimal
eventual path between any pair of nodes (i, j), the loop of k = 1, · · · , N ensure that hij converge to the final
correct solution. This happens for all pair of node simultaneously, thus all hij are computed simultaneously.
(2) If at some point before the loop of k = 1, · · · , N is finished, some of hij are already converged. Theorem
4A guarenttes that continued tightening does not cnange hij any more.
We note that although minimal transitive affinity is uniquely defined, the edge function (the function
defined on the edges) which satisfy the transitive affinity inequality is not unique: for any {hij} who
satisfy the transitive affinity inequality, {2hij} also satisfies the inequality. This is not a problem, however.
Starting from wij, our algorithm compute the minimal increases necessary for {hij} to satisfy the transitive
affinity inequality. This gives the unique maximal transitive affinity.
3
Transitive dissimilarity and closure of a dissimilarity graph
The concepts and results in §2 for affinity graphs can be extended to dissimilarity graphs where the edge
weights D = (dij) measure the “dis-similarity” or “distance”. The “transitive dissimilarity” (or “transitive
distance”) on path Pij is defined as
f (Pij) = max (di,k , d
, · · · , d
, d
1
k1,k2
km
k
−1 ,km
m ,j ).
(16)
6

---

Fixing i, j, transitive dissimilarity depends on the particular path. Thus we define minimal transitive
dissimilarity (analog of shortest path) between i, j as
gij = min f (Pij).
(17)
Pij
We can easily show
gij ≤ dij.
(18)
For affinity graphs considered in §2, the maximal transitive affinity there satifies the ultra-metric in-
equality (see Theorem 1). For dissimilarity graphs considered here, the minimal transitive dissimilarity
satifies the similar ultra-metric inequality:
Theorem 5. For any weighted dissimilarity graph, the minimal transitive dissimilarity between any pair
of vertices satisfies the ultra-metric inequality
gij ≤ max(gik, gkj).
(19)
The proof is identical to the proof for Theorem 1. Therefore, {gij} is consistent with the transitivity of
dissimilarity relationship. We therefore define
Definition 2. The transitive closure of weighted dissimilarity G is formed by the minimal transitive
dissimilarity {gij}.
Computing gij by its original definition, Eq.(17), is farily complicated. Instead we can efficiently
compute them using the ultra-metric inequality (following the same analysis in §2.4):
Theorem 6. The transitive closure of a dissimilarity graph can be equivalently computed by reducing
edge dissimilarities such that the ultra-metic inequality is satisfied.
Intuitively, we can see this from Eq.(18). The transitive closure of a dissimilarity graph can be computed
using the same Floyd-Warshall algorithm in §2.6, with Line 1 replaced by G = D, and Line 5 replaced by
gij = min(gij, max(gik, gkj)).
4
Transitive closure based on the triangle inequality
In §3, the transitive closure of a weighted dissimilarity graph is formed by the minimal transitive dissim-
ilarity which obeys the ultra-metric inequality Eq.(19). The ultra-metric inequality is a stronger form of
the triangle inequality. Indeed, the definition of transitive dissimilarity of Eq.(16) is a stronger form of
transitivity (dissimilarity does not increase as hops increase).
Here we show that by modifying the definition of the transitive dissimilarity (to a weaker form), the
resulting minimal transitive dissimilarity satisfies the triangle inequality Eq.(14) and the original Floyd-
Warshall algorithm. The minimal transitive dissimilarity is in fact, the usual shortest path distance.
The main purpose of this section is show that transitive dissimilarity of §3 is an natural extension of
the usual shortest path problem. Another purpose is to motivate the development of §4.2 on the transitive
affinity which satisfy some kind of triangle inequality, a softer version of the transitive affinity introduced
in §2.
7

---

4.1
Transitive closure of dissimilarity graphs w.r.t. the triangle inequality
Instead of the definition of Eq.(16), we redefine the “transitive dissimilarity” on path Pij as
f (Pij) = di,k + d
+ · · · + d
+ d
1
k1,k2
km
k
−1 ,km
m ,j .
(20)
This is a weaker form of transitivity dissimilarity, which increase as hops increase. This definition satisfies
the associativity. The minimal transitive dissimilarity {gij} is defined to be the transitive dissimilarity
between (i, j) that gives the minimal value, in similar fashion as in Eq.(17). One can see that this is just
the standard shortest path distance.
It is known that the shortest path distance satisfies
Theorem 5A. For any dissimilarity graph, the minimal transitive dissimilarity defined through Eq.(20)
and Eq.(17) satisfies the triangle inequality
gij ≤ gik + gkj.
(21)
Although this is obvious, we give a proof as follows (see proof of Theorem 1). Pij is a path starting at i
and ending at j. (Pik, Pkj) is a path starting at i, going through k, and ending at j. Clearly {(Pik, Pkj)}
is a subset of {Pij}. Thus we have
gij
= min f (Pij)
Pij
≤
min
f (Pik, Pkj)
(Pik,Pkj )
=
min [f (Pik) + f (Pkj)]
(Pik,Pkj )
= min f (Pik) + min f (Pkj)
Pik
Pkj
= gik + gkj.
Following Definition 2, we can define
Definition 3. The transitive closure of a dissimilarity graph w.r.t. the triangle inequality is formed by
the minimal transitive dissimilarity defined through Eq.(20) and Eq.(17).
We can show that the minimal transitive dissimilarity {gij} is smaller than the original dissimilarities,
the inequality of Eq.(18). Following Theorem 6, we can prove
Theorem 6A. The transitive closure of a dissimilarity graph w.r.t. the triangle inequality can be equiv-
alently computed by iteratively reducing edge dissimilarities when tightening the sub-optimal condition,
i.e., to satisfy the triangle inequality.
This transitive closure can be computed using the original Floyd-Warshall algorithm, i.e., the algorithm
in §2.6, with Line 5 replaced by gij = min(gij, gik + gkj).
Therefore, given a dissimilarity graph G, we can compute the minimal transitive dissimilarity defined
through Eq.(20) and Eq.(17). This forms the transitive closure of G w.r.t. the triangle inequality.
The benefit of transitive closure w.r.t. the triangle inequality is that the edge weights are modified
(reduced) relatively small (in comparison to the transitive closure w.r.t. ultra-metric inequality).
4.2
Transitive closure of affinity graphs w.r.t. the harmonic triangle inequality
The concept of transitive closure of a dissimilarity graph w.r.t. to triangle inequality, discussed in §4.1,
can be extended to affinity graphs.
8

---

Although the ultra-metric inequality of distance metric has a natural counterpart in affinity measures
as shown in Theorem 2 in §2.3, the triangle inequality of distance metric has no clear counterpart in affinity
measures.
The simplest and perhaps most natural counterpart is obtained by assuming that affinity is inversely
proportional to distance: sij = const/dij. From this, we obtain
1
1
1
≤
+
(22)
sij
sik
skj
We call this the “harmonic triangle inequality” since it resembles the harmonic average:
1
= 1 ( 1 + 1 ).
<x>
2 x1
x2
With this, we can define a new transitive affinity, similar to the transitive dissimilarity of Eq.(20),
1
1
1
1
1
T(Pij ) = t(Pij),
=
+
+ · · · +
+
.
(23)
t(Pij)
wi,k
w
w
w
1
k1,k2
km
k
−1 ,km
m ,j
in contrast to Eq.(5). Clearly, this transitive affinity satisfies associativity. From this, we can define the
maximal transitive affinity through Eq.(6). Similar to Theorem 1, we have
Theorem 1A. For any affinity graph, the maximal transitive affinity defined through Eq.(23) and Eq.(6)
satisfies the harmonic triangle inequality Eq.(22).
The proof is the same as for Eq.(21)). This maximal transitive affinity forms the transitive closure of
an affinity graph:
Definition 4. The transitive closure of an affinity graph w.r.t. the harmonic triangle inequality is defined
by the maximal transitive affinity defined through Eq.(23) and Eq.(6).
This transitive closure can be computed using the same Floyd-Warshall algorithm in §2.6, with Line 5
replaced by hij = max[hij, hikhkj/(hik + hkj)].
The benefit of this transitive closure w.r.t. the harmonic triangle inequality is that edge weights are
modified (increased) relatively small (in comparison to the transitive closure w.r.t. ultra-metric inequality
in §2.4).
5
Applications of transitive closure
Here we discuss practical applications of transitive closure of weigted graphs.
First, in transitive closure, the originally not-so-densely connected subgraph structures become more
dense, therefore this facilitates the discovery of these dense subgraph structures, i.e., communities in the
network. In this direction, we will discuss an application to protein interaction in §7-8.
Second, in standard web link structure analysis, the web is represented by an unweighted directed
graph. Since our approach emphasizes weighted graphs, we can incorporate webpage content into the link
structure by weighting the link with the cosine similarity between the two webpage word contents. In this
way, the transitive affinity along a path decreases with the number of edges because its strength is the
weakest link between i, j. This is more natural than unweighted link analysis approaches.
Third, transitive closure provides a way to update affinity weights in a changing environment. Suppose
we are given a social network. After a while two persons get married. This marriage will lead to a series
of changes in the social network. Transitive closure provides a quantitative way to update the network
weights. First the edge weight between the two persons in the graph is suddenly increased to maximum.
9

---

Second, the affinity weights between their in-laws are increased such that the transitive inequality holds
for every node triple, etc.
6
Cliques on a weighted graph
A clique is the tightest structure or the densest subgraph in an unweighted graph, because every nodes
in a clique connect to every other nodes. We generalize the concept of clique to weighted graphs and
introduce an algorithm to compute them. The generalization is based on the theorem due to Motzkin and
Straus (Motzkin and Straus, 1965) which relates maximal cliques of an unweighted undirected graph to
the optimization of a quadratic function.
Let G = (V, E) be an unweighted undirected graph of n = |V | vertices and |E| edges with adjacency
matrix A. Define a vector x = (x1, · · · , xn)T on the vertices, i.e., x ∈ Rn. Consider the optimization
problem:
max J(x) = xTAx
(24)
x∈Sn
where x is restricted to the unit simplex Sn defined as
Sn :
x1 + · · · + xn = 1, xi ≥ 0, ∀i.
(25)
The nonzero elements in the solution vector x play an important role. In particular, we define a characteris-
tic vector of a subset C of vertices as xC = (xc1, · · · , xcn)T, where xci = 1/|C| if i ∈ C, xci = 0 otherwise. The
following theorem make the connection between vertices corresponding to nonzero elements to maximal
cliques.
Theorem 7[Motzkin and Straus]. (1) Subset C is the largest maximal clique if and only if its characteristic
vector is a global optimal solution of the optimization problem; (2) Subset C is a maximal clique if and
only if its characteristic vector is a local optimal solution of the above optimization problem.
The Motzkin-Straus Theorem provides a convenient formalism to generalize the concept of cliques to
weighted graphs.
Definition 5. Generalized cliques in a weighted graph with adjacency matrix A. The subset of vertices
corresponding to the nonzero elements in the optimal solution x∗ form a clique in A.
The key to this generalization is the recognition of the L1-type constraint of Eq.(25) in the quadratic
programming problem of Eq.(24) (The Lp-norm of a vector x in n-dimensional space is defined as ||x||p =
(
n
|x
j=1
j |p)1/p, 1 ≤ p ≤ ∞.) It is well-known (Tibshirani, 1996; Hastie et al., 2001) that this L1-type
constraint leads to sparse solutions, i.e., many if not most of entries in the final optimal solution x∗ are zero.
This sparsity property of the solution is the theoretical basis for our generalization of the Motzkin-Straus
formalism to define cliques in weighted graphs. On the other hand, if the L1-type constraint of Eq.(25) is
replaced by a L2 constraint:
x2
i
i = 1 and xi ≥ 0, the solution will not be sparse — almost every node
will be in the clique. 1
The quadratic programming problem of Eq.(24) can be solved by a simple method developed in the
biological evolution field (Pelillo et al., 1999). The method is an iterative algorithm updating a current
1Using L2 constraint, the solution is the principal eigenvector of A. By Perron’s Theorem, all entries of the principal
eigenvector are nonnegative.
10

---