"가중치 크리크"문제로 들립니다. 예 : 예 : r = 최대 호환성을 가진 네트워크에서 5 명/최대 C (5,2) 쌍의 합계.
구글 "weighted clique"알고리즘 - "clique percolation"→ 3k 히트.
하지만 나는 그것을 이해하고
제어이기 때문에 (저스틴 껍질의 방법 과 함께 할 것입니다 그들로부터 최고의 N3 트리플을 N2 최고의 쌍을 것입니다 ... 은 ... N2, N3를 조정 쉽게 결과의 실행/품질을 절충.)
18 개를 추가하여 구현시 다음 커밋을 추가 할 수 있습니다.
@Jose, nbest [] 시퀀스가 어떤 역할을하는지 알아 보는 것은 흥미로울 것입니다.
#!/usr/bin/env python
""" cliq.py: grow high-weight 2 3 4 5-cliques, taking nbest at each stage
weight ab = dist[a,b] -- a symmetric numpy array, diag << 0
weight abc, abcd ... = sum weight all pairs
C[2] = [ (dist[j,k], (j,k)) ... ] nbest[2] pairs
C[3] = [ (cliqwt(j,k,l), (j,k,l)) ... ] nbest[3] triples
...
run time ~ N * (N + nbest[2] + nbest[3] ...)
keywords: weighted-clique heuristic python
"""
# cf "graph clustering algorithm"
from __future__ import division
import numpy as np
__version__ = "denis 18may 2010"
me = __file__.split('/') [-1]
def cliqdistances(cliq, dist):
return sorted([dist[j,k] for j in cliq for k in cliq if j < k], reverse=True)
def maxarray2(a, n):
""" -> max n [ (a[j,k], (j,k)) ...] j <= k, a symmetric """
jkflat = np.argsort(a, axis=None)[:-2*n:-1]
jks = [np.unravel_index(jk, a.shape) for jk in jkflat]
return [(a[j,k], (j,k)) for j,k in jks if j <= k] [:n]
def _str(iter, fmt="%.2g"):
return " ".join(fmt % x for x in iter)
#...............................................................................
def maxweightcliques(dist, nbest, r, verbose=10):
def cliqwt(cliq, p):
return sum(dist[c,p] for c in cliq) # << 0 if p in c
def growcliqs(cliqs, nbest):
""" [(cliqweight, n-cliq) ...] -> nbest [(cliqweight, n+1 cliq) ...] """
# heapq the nbest ? here just gen all N * |cliqs|, sort
all = []
dups = set()
for w, c in cliqs:
for p in xrange(N):
# fast gen [sorted c+p ...] with small sorted c ?
cp = c + [p]
cp.sort()
tup = tuple(cp)
if tup in dups: continue
dups.add(tup)
all.append((w + cliqwt(c, p), cp))
all.sort(reverse=True)
if verbose:
print "growcliqs: %s" % _str(w for w,c in all[:verbose]) ,
print " best: %s" % _str(cliqdistances(all[0][1], dist)[:10])
return all[:nbest]
np.fill_diagonal(dist, -1e10) # so cliqwt(c, p in c) << 0
C = (r+1) * [(0, None)] # [(cliqweight, cliq-tuple) ...]
# C[1] = [(0, (p,)) for p in xrange(N)]
C[2] = [(w, list(pair)) for w, pair in maxarray2(dist, nbest[2])]
for j in range(3, r+1):
C[j] = growcliqs(C[j-1], nbest[j])
return C
#...............................................................................
if __name__ == "__main__":
import sys
N = 100
r = 5 # max clique size
nbest = 10
verbose = 0
seed = 1
exec "\n".join(sys.argv[1:]) # N= ...
np.random.seed(seed)
nbest = [0, 0, N//2] + (r - 2) * [nbest] # ?
print "%s N=%d r=%d nbest=%s" % (me, N, r, nbest)
# random graphs w cluster parameters ?
dist = np.random.exponential(1, (N,N))
dist = (dist + dist.T)/2
for j in range(0, N, r):
dist[j:j+r, j:j+r] += 2 # see if we get r in a row
# dist = np.ones((N,N))
cliqs = maxweightcliques(dist, nbest, r, verbose)[-1] # [ (wt, cliq) ... ]
print "Clique weight, clique, distances within clique"
print 50 * "-"
for w,c in cliqs:
print "%5.3g %s %s" % (
w, _str(c, fmt="%d"), _str(cliqdistances(c, dist)[:10]))
이 속도가 빨라졌습니다! 감사! – Jose