복잡 한 네트워크 커 뮤 니 티 구조 발견 알고리즘 - python network x clique 침투 알고리즘 기반

머리말
    최근 에 업무 데이터 분석의 수요 로 인해 지역 사 회 를 보면 관련 된 것 이 약간 많 고 igraph C library 를 바탕 으로 하 는 방법 (http://blog.csdn.net/a_step_further/article/details/51176973) 그리고 kclique 에서 파생 된 clique 침투 알고리즘 을 사용 하려 고 했 을 때 igraph C library 가 기 존의 api 를 제공 하지 않 은 것 을 발 견 했 습 니 다. 게 으 른 사람 에 게 는 불행 합 니 다.network x 라 는 python 가방 에 있 는 것 을 발 견 했 습 니 다. (또한 지역 사회 에서 발견 할 수 있 는 유일한 알고리즘 입 니 다) 그래서 실 랑 이 를 하 며 처리 과정 을 기록 하여 같은 친구 들 이 참고 하도록 하 세 요.
준비 작업
    network x 설치 시 의존 decorator, setuptools 같은 가방 은 모두 설치 해 야 합 니 다.
networkx   https://networkx.github.io
decorator  https://pypi.python.org/pypi/decorator
setuptools  https://pypi.python.org/pypi/setuptools
     설치 후 python 인 터 랙 션 환경 에 들 어가 테스트 합 니 다.

 import networkx as nx

잘못 보고 하지 않 았 다 면 기초 작업 을 준비 한 셈 이다.network x 라 는 네트워크 분석 패 키 지 를 사용 할 수 있 습 니 다.본 고 는 인터넷 에서 지역사회 구조의 발견 에 초점 을 맞 추 었 기 때문에 network x 의 기본 적 인 사용 방법 은 생략 되 었 고 여러분 은 스스로 구 글 을 사용 할 수 있 습 니 다.
clique 침투 알고리즘 안내
    하나의 그림 G 에 있어 서 만약 에 그 중의 완전 서브 맵 (임의의 두 노드 사이 에 모두 변 이 존재 한다) 이 있 으 면 노드 수 는 k 이 고 이 완전 서브 맵 은 k - clique 라 고 할 수 있다.
    더 나 아가 만약 에 두 개의 k - clique 사이 에 k - 1 개의 공 통 된 노드 가 존재 한다 면 이 두 개의 clique 는 '인접' 이 라 고 부른다.서로 인접 한 이러한 clique 는 최대 집합 을 구성 하면 한 지역 사회 라 고 할 수 있다.아래 의 첫 번 째 그림 은 두 개의 3 - clique 가 하나의 지역 사 회 를 형 성 했 고 두 번 째 그림 은 지역 사 회 를 중첩 하 는 설명도 임 을 나타 낸다.
    -->  
 
   network x 에서 실 현 된 clique 침투 알고리즘 인 터 페 이 스 는 다음 과 같 습 니 다.
커 뮤 니 티 찾기 (상위 코드)
 무방 향 무 권 도 를 예 로 들다

#!/usr/bin/python
#coding:utf-8
import sys
import networkx as nx
import time

def find_community(graph,k):
    return list(nx.k_clique_communities(graph,k))

if __name__ == '__main__':
    if len(sys.argv) < 2:
        print "Usage: %s <InputEdgeListFile>" % sys.argv[0]
        sys.exit(1)

    #      、   
    edge_list_file = sys.argv[1]
    wbNetwork = nx.read_edgelist(edge_list_file,delimiter='\t')
    print "     ：%d" % wbNetwork.number_of_nodes()
    print "    ：%d" % wbNetwork.number_of_edges()

    #  kclique    
    for k in xrange(3,6):
        print "############# k : %d ################" % k
        start_time = time.clock()
        rst_com = find_community(wbNetwork,k)
        end_time = time.clock()
        print "    ( )：%.3f" % (end_time-start_time)
        print "      ：%d" % len(rst_com)

알고리즘 출력 및 토론 
단일 컴퓨터 64G 메모리 의 기계 에서 몇 개의 서로 다른 규모 의 네트워크 를 테스트 했 는데 해당 하 는 출력 은 다음 과 같다.
  
이 알고리즘 은 단기 적 으로 10 만 이하 노드 중 소 규모 네트워크 지역사회 구 조 를 계산 하 는 데 적합 하 다 는 것 을 알 수 있다.대규모 소 셜 네트워크 서비스 에 대해 서 는 분포 식 군집 을 써 야 한다.