Facebook Network에서 Community Detection

(Facebook 네트워크 DataSet : snap.stanford.edu 의 Facebook 수집 정보)

[Option 1] Modularity Maximization

–Network-Centric Community Detection 기법 중 Modularity Maximization 기법을 사용하여 커뮤니티를 도출하고 Ground Truth와의 다음 비교를 통해 가장 Ground truth와 유사도가 높은 커뮤니티 구성을 제시하시오.

•NMI

•Accuracy

- Modularity Maximization 수식

- NMI ( Normalized Mutual Information) 수식

- Accuracy 수식

결과값

Ego-Network (circle num)	NMI	Accuracy	Balaced_Accuracy
0 (24)	0.315198369925	0.708784596871	0.504977375469
107 (9)	0.40327795919	0.606028183716	0.569606621639
348 (14)	0.439735454474	0.176045321946	0.486369035413
414 (7)	0.672568174712	0.78936146336	0.715865535473
686 (14)	0.34900620265	0.379027658968	0.504352021915
698 (13)	0.892580698441	0.869803921569	0.712850224836
1684 (17)	0.446600063726	0.796311011582	0.556930216647
1912 (46)	0.587107636673	0.802668113234	0.553714011307
3437 (32)	0.759151157085	0.654209621993	0.525378237688
3980 (17)	0.566945313748	0.786576168929	0.521568166818

실행과정 유의사항

snap의 Facebook 데이터에서의 Ground-Truth 데이터 값과 비교하기 위하여 나누려 하는 커뮤니티의 수를 입력 해야 하는데 Ground-Truth 의 커뮤니티 수에 맞게 입력해야 합니다.  위의 표에 맞도록 입력해야 합니다. - Example   ( 오른쪽 괄호 안의 값 ) 0.edges 파일에 대한 커뮤니티 도출시 입력 Community 수의 값 : 24 107.edges 파일에 대한 커뮤니티 도출시 입력 Community 수의 값 : 9 실행 과정에서 NMI 값에 대한 함수 , Accuracy 값에 대한 함수의 입력 Parameter는 커뮤니티 도출이 된 데이터가 2차원 형태의 List 데이터를 요구합니다. K-means 함수 실행 후의 [1,1,1,0,0,0,1,2,2,] 값                                X 노드의 값을 가지고 있는 List  [ [ 1,2,3,4], [5,6,7,8], [10,12] ]        O

설정 변경 사항

Edges 의 데이터에서의 커뮤니티 분할 결과의 노드들이 Ground-Truth 에서 읽어 드린 데이터의 노드들과 값이 다릅니다. 양 측에 서로 존재하지 않는 노드들이 존재하여 전체 노드의 수 N 값이 달라지게 되어 이를 맞도록 수정하기 위하여 양 측 데이터에서 한 쪽에만 존재하는 노드들을 제외하였습니다. 즉, 양 쪽 데이터 모두에 존재하느 노드들만 남겨놓고 실행하였습니다.

소스 코드

# -*- coding: utf-8 -*- import dircache import os.path import networkx as net import networkx.algorithms as algo import matplotlib.pyplot as plt import numpy as np import numpy.linalg as la import Pycluster from scipy import * #circles num #0 = 24, 107 = 9, 348 = 14, 414 = 7, 686 = 14, 698 = 13, 1684 = 17, 1912 = 46, 3437 = 32, 3980 = 17 def my_NMI(circle1, circle2):   #NMI 값을 반환하는 함수 result_value = 0 cc_temp = [] for i in circle1: for j in i: if not j in cc_temp: cc_temp.append(j) n = len(cc_temp) circle1_num = [] for i in circle1: circle1_num.append(len(i)) circle2_num = [] for i in circle2: circle2_num.append(len(i)) #print circle1_num #print circle2_num #print n circle1_h = my_h(circle1_num, n) circle2_h = my_h(circle2_num, n) denominator = np.sqrt( (circle1_h * circle2_h) ) numerator = 0 for i in range(0, len(circle1)): for j in range(0, len(circle2)): x = same_data_num(circle1[i], circle2[j] ) x = float(x)/n #print "same data %f" % x if not x == 0: #print "not 0" numerator +=  x * np.log10( x / ((float(circle1_num[i])/n)*(float(circle2_num[j])/n))  ) result_value = numerator / denominator return result_value def same_data_num(circle1, circle2): #NMI 계산에 필요한 함수(양쪽 써클에 동일하게 존재하는 노드의 수) result_value = 0 for i in circle1: for j in circle2: if i == j: result_value += 1 return result_value def my_h(circle_num, n):  #NMI 계산에 필요한 함수 result_value = 0 for i in circle_num: if not i  == 0: x = float(i) / n result_value += x * np.log10(x) #print result_value return result_value def my_accuracy(circle1, circle2):   #  Accuracy 값을 반환하는 함수 result_value = 0 all_list = [] for i in circle1: for j in i: all_list.append(j) pair_list = [] for i in range(0, len(all_list)): for j in range(i, len(all_list)): if all_list[i] != all_list[j]: pair_list.append( [ all_list[i], all_list[j] ] ) a_value = 0 d_value = 0 for pair in pair_list: c1 = 0 c2 = 0 for x in circle1: if pair[0] in x and pair[1] in x: c1 = 1 for x in circle2: if pair[0] in x and pair[1] in x: c2 = 1 if c1 == 1 and c2 == 1: a_value += 1 if c1 == 0 and c2 == 0: d_value += 1 n = len(all_list) result_value = float(a_value + d_value) / ( n*(n-1)/2) return result_value list = dircache.listdir('.') g = net.Graph() for item in list: filename, extension = os.path.splitext(item) if extension in '.edges':   # edges 파일에 데이터를 읽어들여 egoNetwork Graph 생성 print 'add information to g(Graph) from ' + item f = file(item) pre ='' after='' isAdd = 0 allF = f.read() for x in allF: if x == ' ': isAdd = 1 elif x == '\n': isAdd = 0 g.add_edge(int(pre), int(after)) g.add_edge(int(filename), int(pre)) g.add_edge(int(filename), int(after)) pre='' after='' else: if isAdd == 0: pre += x else: after += x #Modularity Maximization 에 기반한 커뮤니티 도출 시작 print "%s community number : " % filename dimen = input() g_nodes_num = g.number_of_nodes() g_edges_num = g.number_of_edges() A = [] for i in g: temp = [] for j in g: if g.has_edge(i, j): temp.append(1) else: temp.append(0) A.append(temp) B = [] k = 0 l = 0 for i in g: temp = [] for j in g: temp.append( (A[k][l] - ( (g.degree(i)*g.degree(j)) / float(2*g_edges_num) ) ) ) l += 1 B.append(temp) k += 1 l = 0 B_mat = np.mat(B) w, v = la.eig(B_mat) V = [[0.0 for i in range(1,3)] for k in range(1, g_nodes_num+1)] V = np.mat(V)   # top two eigenvector  V[:,0] += v[:,0] V[:,1] += v[:,1] #only use first dimensional value labels = Pycluster.kcluster(V, dimen) #labels # W = np.diag((w[0], w[1])) eigenvalue is not used circle = []   k = 0 for i in range(0, dimen): k = 0 temp = [] for j in g: if labels[0][k] == i: temp.append(j) k += 1 circle.append(temp) k = 0 f = open('%s.mmCircles' % filename, 'w') for x in circle: f.write("circle%d\t" % k ) for y in x: f.write("".join(str(y))) f.write("\t") f.write('\n') k += 1 f.close() #modularity 이용 커뮤티니 나눈뒤 circle에 나뉜 값을 저장 with open("%s.circles" % filename) as readF: readData = readF.read() readData = readData.split('\n') readData.remove('') readString = [row.split('\t')[1:] for row in readData] gt_circle = [] for i in readString: temp = [] for j in i: temp.append(int(j)) gt_circle.append(temp)                #circle 안에는 나뉘어진 커뮤니티 정보                #gt_circle 안에는 읽어들인 Ground-Truth 커뮤니티 정보                #gt circle 에는 있는데 circle에 없는 경우 gt_circle 에서 지우기 remove_list = [] for list_gt in gt_circle: for value_gt in list_gt: sameValue = 1 for list_cc in circle: for value_cc in list_cc: if value_gt == value_cc: sameValue = 0 if sameValue == 1: #print value_gt remove_list.append(value_gt) for i in remove_list: for h in range(0, len(circle)): try: gt_circle[h].remove(i) except ValueError: pass #circle 에는 있는데 gt_circle에 없는 경우 circle 에서 지우기 remove_list = [] for list_gt in circle: for value_gt in list_gt: sameValue = 1 for list_cc in gt_circle: for value_cc in list_cc: if value_gt == value_cc: sameValue = 0 if sameValue == 1: #print value_gt remove_list.append(value_gt) for i in remove_list: for h in range(0, len(circle)): try: circle[h].remove(i) except ValueError: pass #양쪽에 없는 값들 지우기 끝 print "%s's NMI : " % filename print my_NMI(circle, gt_circle) print "%s's Accuracy : " % filename print my_accuracy(circle, gt_circle) g = net.Graph()

`