목적

마지막 기사에서 "분산 그래프 분석기 sotera/distributed-graph-analytics (이하 Sotera-DGA)"의 louvain 방법 샘플을 실행했지만 결과의 타당성을 알지 못했기 때문에 곳곳에서 자주 사용되었습니다. 하고 있는 python-louvain의 출력 결과와 비교 검증해 보자.

방법

데이터 준비

검증을 위한 데이터로 소셜 네트워크 연구에서 자주 사용되는 karate club를 사용한다.
아래의 코드로 Sotera-DGA용 포맷으로 출력한다.

karate.py

import networkx as nx
graph=nx.karate_club_graph()
for edge in graph.edges():
    print str(edge[0]+1) + "," + str(edge[1]+1)

상기 코드로 출력된 데이터 karate.csv

작업 실행

작업 실행 방법에 대한 자세한 내용은 여기을 참조하십시오.

hadoop fs -put karate.csv /user/hdfs/input
bin/dga-yarn-giraph louvain "/user/hdfs/input/karate.csv" "/user/hdfs/output" -ca io.edge.reverse.duplicator=true -ca minimum.progress=0

Sotera-DGA에서는 양방향 접속의 그래프가 아니면 louvain법을 적용할 수 없고, 작업이 실패한다. 파라미터 ca io.edge.reverse.duplicator=true를 붙이면, karate.csv와 같이 단방향의 노드 접속 밖에 기술되어 있지 않은 데이터가, 양방향 접속되고 있는 것으로 간주되어 읽힌다.
매개변수-ca minimum.progress=0는 기본값입니다. 지정하지 않으면, 값의 설정 부분에 버그가 있어 2000등의 모르는 값이 되어 해석이 도중에 끝나 버리므로, 수정 pull-req (을)를 보내고 있다.

이번에는 아래의 순서로 분석 결과를 확인한다.
(1) 출력되는 데이터를 이 스크립트에서 networkx로 읽을 수있는 json 형식으로 변환합니다.
(2) 이 스크립트에서 matplotlib.pyplot에서 그래프 출력
(3) 이 스크립트에서 modularity (Q 값)도 계산한다.

결과

Sotera-DGA에 의한 결과

Sotera-DGA에서 louvain 방법을 실행하면 분석 알고리즘의 반복 별 상태가 다음과 같이 출력됩니다.

hadoop fs -ls /user/hdfs/output/giraph_*
-rw-r--r--   1 nobody supergroup        630 2016-06-25 04:05 /user/hdfs/output/giraph_0/part-m-00001
-rw-r--r--   1 nobody supergroup        132 2016-06-25 04:06 /user/hdfs/output/giraph_1/part-m-00001

파일 내용은 여기입니다.
도중 경과의 데이터에서 덴드로그램을 만들 수도 있습니다.
일단 giraph_[0-1]의 데이터를 바탕으로 최상위그룹핑 결과를 만든다.
데이터 형식은 이전 문서를 참조하십시오.

이것을 이 스크립트에서 networkx로 읽을 수있는 json 형식으로 변환하고 이 스크립트에서 matplotlib.pyplot에서 그래프 출력하면 아래와 같았다.

또한 Q값을 계산하면 0.409681130835였다.

python-louvain의 결과

karate_club의 데이터를 python-louvain의 best_pertition으로 해석한 결과는 아래와 같다.

또한 Q값을 계산하면 0.418803418803이었다.
Sotera-DGA 쪽은 12번의 노드가 잘 분리되어 있지 않은 것처럼 보인다.

파라미터 조정

Sotera-DGA의 LouvainRunner에는 minimum.progress와 progress.tries라는 두 가지 매개 변수가 있습니다.
htp // 소테라. 기주 b. 이오 / st 리부테 dg 등 ph - 아나 ly cs / ぉ ゔ ぁ ん / # ぉ ゔ ぁ
이 2개의 파라미터는 Q값의 변화량에 따라 계산을 도중에 종료시키기 위한 것으로, 원논문에는 존재하지 않는 Sotera-DGA의 독자적인 파라미터인 것 같다. (원래의 louvain법은 노드가 소속하는 그룹이 변화하지 않게 되면 종료였을 것이다.)

또한, 이 파라미터는 소스의 여기 의 처리 종료 판정으로 사용되고 있지만, 처리가 도중에 끝나지 않게 progress.tries를 10000등으로 하면(자) python-louvain와 같은 결과가 얻어졌다.

bin/dga-yarn-giraph louvain "/user/hdfs/input/karate.csv" "/user/hdfs/output" -ca io.edge.reverse.duplicator=true -ca minimum.progress=0 -ca progress.tries=10000 

요약

sotera-DGA에 의해 python-louvain과 동등한 해석 결과를 얻는 수단도 알았으므로, 다음번은 보다 큰 데이터로 검증해 보고 싶다.