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() 

상호성 공식은 "트위터는 소셜 네트워크인가?" 논문의 P.98을 참고한다.

문제 2 에서는 Homework-2 에서 생성한 Twitter 네트워크와 Facebook 네트워크에 대하여 다음을 조사한다. Twitter 네트워크에서 팔로어 수의 분포와 Facebook 네트워크에서 친구 수의 분포, 그리고 각 분포에 대해 다음 멱함수(power-law) 분포 함수의 지수값을 도출한다.   

"트위터는 소셜 네트워크인가?" 논문의 P. 99~100를 참고하여 팔로어 수/ 친구 수 분포에 관한 CCDF 을 도시한다.

 import networkx as net

 import dircache

 import os.path

 list = dircache.listdir('.')

 g = net.DiGraph()

 for item in list:

filename, extension = os.path.splitext(item)

if extension in '.edges':

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

 g2 = g.to_undirected()

 denominator = g2.number_of_edges()  // 1336678

 numerator = g.number_of_edges() - g2.number_ofedges() // 425826

 reciprocity = numerator / denominator // 0.31857036623629625

                            일반 그래프 (x축 : 팔로어의 수   y축 : 노드의 수)

                                loglog-그래프  (

                                일반 그래프 (

                                               Twitter

   a = 592.06422635    b = -2.06651771

                                            Facebook

a = 631.61329871   

 Graph 생성 edges 추가 후

inlist = []

#각 노드들의 팔로어수 ( 자기자신을 가리키는 degree 의 수 )

for i in g.nodes():

inlist.append( g.in_degree(i) )

#facebook 의 경우 DiGraph 가 아니기 때문에 g.in_degree(i) 를 g.degree(i) 로 변경 후 사용한다

#팔로어 수 중에 가장 큰 값을 찾는다

maxInDegree = inlist[0]

for i in inlist:

    if i>maxInDegree:

        maxInDegree = i

#degree 의 수를 x 리스트에 저장

#전체에서 특정 degree 값 이상이 차지하는 비율 값을 y 리스트에 저장

totalValue = len(inlist)

cumRatio = 0;

x = []

y = []

for i in range(maxInDegree+1):

    count = 0

    for j in inlist:

     if j >= i:

     count = count + 1

    cumRatio = float(count) / totalValue

    x.append(i)

    y.append(cumRatio)

#그래프 그리기    

plt.loglog(x, y)

plt.show()

#CCDF 그래프데이터 값을 txt파일로 만들어 저장하고 불러와 사용하기

f = open("ccdfData.txt", 'w')

totalValue = len(inlist)

cumRatio = 0;

for i in range(maxInDegree+2):

count = 0

for j in inlist:

if j >= i:

count = count + 1

cumRatio = float(count) / totalValue

if i == maxInDegree + 1:

data = "%d %f" % ( i, cumRatio )

f.write(data)

else:

data = "%d %f\n" % ( i, cumRatio )

f.write(data)

f.close()

with open("ccdfData.txt") as f:

readData = f.read()

readData = readData.split('\n')

x = [row.split(' ')[0] for row in readData]

y = [row.split(' ')[1] for row in readData]

#그래프 그리기

plt.loglog(x, y)

plt.show()

by = []

for i in range(maxInDegree+1):

count = 0

for j in inlist:

if j == i:

count = count + 1

by.append(count)

x.remove(0)  # 로그값을 취해 계산하기 위하여 x 데이터의 0값을 지운다

y.remove(1) # x 데이타에서 지워진 0에 대응되는 y 데이터값을 지운다

def func( x, a, b):    #func 함수를 식에서 양변에 log 를 취한 값의 함수 형식으로 변경하여 정의

return math.log10(a) - b*x    # x 와 y 데이터는 외부에서 log값으로 변경하여 사용한다

#x 데이터를 로그값으로 변경하여 리스트로 저장

logx = []

for i in x:

logx.append(math.log10(i))

#y 데이터를 로그값으로 변경하여 리스트로 저장

logy = []

for i in y:

logy.append(math.log10(i))

# a 와 b 의 초기값 지정.  a는 로그값을 취하므로 1을 기본값으로 한다. b 는 0으로 기본값 지정

x0 = numpy.array( [1.0, 0.0] )

xdata = numpy.array(logx)

ydata = numpy.array(logy)

#함수에 사용하기 위하여 array 형태로 변경

#분모 sigma 값을 1로 지정

sigma = []

for i in range(len(x)):

sigma.append(1)

#함수에 사용하기 위하여 array 형태로 변경

sigma = numpy.array(sigma)

#함수에 인자값을 넣으며 호출

print optimization.curve_fit(func, xdata, ydata, x0, sigma)

#호출된 a 와 b 값을 확인하여 loglog 그래프에 직선으로 표시되는 식에 맞는 값으로 변경

 Shin

1번 문제는 트위터 그래프의 단방향 관계, 양방향 관계에 대한 이해로 그리 어렵지 않게 완성하였습니다. Edge의 수를 구해서 상호성 공식에 대입하면 쉽게 위와같이 구할 수 있었습니다.

2번 문제는 CCDF 그래프의 개념은 수업시간에 자세히 배워서 알고있었지만 Y축을 어떻게 표현해야할지 매우 막막하고 많이 어려워서 용진오빠에게 많은 도움을 받았습니다. Y축을 구하고 나서 loglog 그래프를 금방 그릴 수 있었습니다. 멱함수 분포에 지수값인 r을 구하는 과정은 교수님께 설명을 들어서 최소자승법 페이지에 있는 공식대로 열심히 계산을 해보았지만, y = ax^(-r) 에서 a를 편미분한 식과 -r을 편미분한 식을 연립하는 과정에서 계산이 되지 않아 다른 방법을 찾아보고 있습니다! 곧 업데이트하겠습니다! 

 Jeong

CCDF 그래프 그리는 것에 대한 y 축에 대한 이해와

matplotlib.pyplot 안에 loglog와 plot 함수에 입력 변수등에 대한 정확한 이해가 가지 않아서 여러가지 데이터를 넣어가며 실행 해본결과 사용법이 어떤 것인지는 알게 된것 같습니다.

데이터를 파일로 만들어 저장하는 것에 대한 것을 확실히 알게 되었고, edges를 추가하면서 사용했던 방법 외에 한줄씩읽어와 split 를 통해 잘라내어 쉽고 효과적으로 데이터를 불러오는 방법을 새로 발견하였습니다. 하지만 멱함수 분포함수의 지수값 도출 부분에 대해 여러가지 경우로 데이터를 만들어 보았지만 틀린 방법으로 구해진듯하여 그래프가 제대로 구해지지 않았습니다. 다른 식으로 테스트해보고 그래프가 비슷하게 나오는 경우를 보아 해결방법을 찾은듯 하였으나 a값과 r값을 구하게 만드는 식을 도출하는데에 어려움이 있어서 마무리 짓지 못하였습니다.

결국 함수를 사용하여 찾아냈습니다. 이전에 한번 인터넷 검색으로 찾아서 봤던 함수인데 잘 안구해지는것 같아 넘어갔었는데 제가 사용을 제대로 못한것 같습니다. 이제라도 확인하게 되어 다행입니다.