# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.8.3 64-bit (conda)
#     name: python383jvsc74a57bd05c6bee9180bd5f215609a25bd8cb44b61e55e337adc560d50a1b40fec4435080
# ---

# +
import matplotlib.pyplot as plt
import scipy as sp
from scipy.io import loadmat
import numpy as np
import time
from skimage.transform import rescale, resize, downscale_local_mean
from skimage import data

import sys
sys.path.append("../../../LocalGraphClustering/")
sys.path.append("../../../LocalGraphClustering/notebooks/")

from localgraphclustering import *

import warnings
warnings.filterwarnings('ignore')

# +
import matplotlib.pyplot as plt
import scipy as sp
from scipy.io import loadmat
import numpy as np
import time
from skimage.transform import rescale, resize, downscale_local_mean
from skimage import data

import sys
sys.path.append("../../../LocalGraphClustering/")
sys.path.append("../../../LocalGraphClustering/notebooks/")

from localgraphclustering import *

import warnings
warnings.filterwarnings('ignore')

import multiprocessing as mp

def clutser_improvement(g,ratio,nprocs):
    records = []
    def wrapper(q_in,q_out):
        while True:
            seed = q_in.get()
            if seed is None:
                break
            R = [seed]
            R.extend(g.neighbors(seed))
            R = list(set(R))
            one_hop = R.copy()
            for node in one_hop:
                R.extend(g.neighbors(node))
            R = list(set(R))
            cond_R = g.set_scores(R)["cond"]
            mqi_output = flow_clustering(g,R,method="mqi_weighted")
            print("2-hop exp. - mqi",len(R),cond_R,len(mqi_output[0]),mqi_output[1])
            sl_output1 = flow_clustering(g,R,method="sl_weighted",delta=0.01)
            print("2-hop exp. - sl_output1",len(R),cond_R,len(sl_output1[0]),sl_output1[1])
            sl_output2 = flow_clustering(g,R,method="sl_weighted",delta=0.1)
            print("2-hop exp. - sl_output2",len(R),cond_R,len(sl_output2[0]),sl_output2[1])
            sl_output3 = flow_clustering(g,R,method="sl_weighted",delta=1)
            print("2-hop exp. - sl_output3",len(R),cond_R,len(sl_output3[0]),sl_output3[1])
            q_out.put((seed,"2-hop",cond_R,mqi_output[1],sl_output1[1],sl_output2[1],sl_output3[1]))
    n = g._num_vertices
    np.random.seed(seed=123)
    seeds = np.random.choice(range(n),size=int(ratio*n), replace=False)
    q_in,q_out = mp.Queue(),mp.Queue()
    procs = [mp.Process(target=wrapper,args=(q_in,q_out)) for i in range(nprocs)]
    for seed in seeds:
        q_in.put(seed)
    for i in range(nprocs):
        q_in.put(None)
    for p in procs:
        p.start()
    ncounts = 0
    t1 = time.time()
    while ncounts < len(seeds):
        ncounts += 1
        record = q_out.get()
        print(ncounts,len(seeds),record[2],record[3],record[4],record[5],record[6])
        print(time.time()-t1)
        records.append(record)
    for p in procs:
        p.join()
    return records

#graph = GraphLocal("com-orkut.ungraph.txt")
graph = GraphLocal("../../dataset/lawlor-spectra-k32.edgelist","edgelist")
g = graph.largest_component()
ratio = 0.005
records = clutser_improvement(g,ratio,40)


# +
colors = ['#1f77b4', '#ff7f0e', '#2ca02c', '#d62728']

# import pickle

# rptr = open("ncp_records_bfs.p","rb")
# records = pickle.load(rptr)
# rptr.close()

improvement = np.array([[i[3]/i[2],i[4]/i[2],i[5]/i[2],i[6]/i[2]] for i in records])

import statsmodels.api as sm
from statsmodels.distributions.empirical_distribution import ECDF


f, ax = plt.subplots(1,1,figsize=(8,4),gridspec_kw={"wspace":0.05})
ax_inset = f.add_axes([0.2,0.6,0.2,0.2])
x_inset = np.array(range(0,101))*0.01

ax_inset.set_xlim(-0.0001,1.02)
ax_inset.set_ylim(-0.0001,1.02)
ax.set_xlim(-0.0001,1)
ax.set_ylim(-0.0001,6)

for i in range(improvement.shape[1]):
    subset = improvement[:,i]
    kde = sm.nonparametric.KDEUnivariate(subset)
    kde.fit(kernel="tri",fft=False,bw=0.03,cut=0,clip=(-1*float("inf"),1))
    ax.plot(kde.support,kde.density,color=colors[i],linewidth=3)
    ax.hist(subset,color=colors[i],bins=100,density=True,alpha=0.2)
    ecdf = ECDF(subset)
    ax_inset.plot(x_inset,ecdf(x_inset),color=colors[i],linewidth=3)

ax_inset.set_title("CDF")
ax_inset.spines['top'].set_visible(False)
ax_inset.spines['right'].set_visible(False)
# ax_inset.spines['left'].set_visible(False)
# ax_inset.spines['bottom'].set_visible(False)
ax.set_xlabel(r"$\phi($"+"Improved) / "+r"$\phi($"+"2-hop BFS)",fontsize=15)
#ax.set_title("Conductance improvement",fontsize=15)
ax.set_ylabel("Probability density",fontsize=15)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.tick_params(axis='y', which='both', length=5,width=2)
ax.tick_params(axis='x', which='both', length=5,width=2)
for tick in ax.xaxis.get_major_ticks():
    tick.label.set_fontsize(15)
for tick in ax.yaxis.get_major_ticks():
    tick.label.set_fontsize(15)

f.legend(ax.get_lines(),["MQI",r"LFI ($\delta=0.01$)",r"LFI ($\delta=0.1$)",r"LFI ($\delta=1$)"],
         fancybox=True, shadow=True,fontsize=15,bbox_to_anchor=(0.7,0.95))
f.savefig("cluster_improvement_BFS.pdf",format='pdf',bbox_inches='tight')

# +
f, ax = plt.subplots(1,1,figsize=(8,4),gridspec_kw={"wspace":0.05})

ax_inset = f.add_axes([0.2,0.6,0.2,0.2])
x_inset = np.array(range(0,101))*0.01

ax_inset.set_xlim(-0.0001,1.02)
ax_inset.set_ylim(-0.0001,1.02)
ax.set_xlim(-0.0001,1)
ax.set_ylim(-0.0001,6)

for i in range(1,improvement.shape[1]):
    subset = improvement[:,i]
    kde = sm.nonparametric.KDEUnivariate(subset)
    kde.fit(kernel="tri",fft=False,bw=0.03,cut=0,clip=(-1*float("inf"),1))
    ax.plot(kde.support,kde.density,color=colors[i],linewidth=3)
    ax.hist(subset,color=colors[i],bins=100,density=True,alpha=0.2)
    ecdf = ECDF(subset)
    ax_inset.plot(x_inset,ecdf(x_inset),color=colors[i],linewidth=3)

f.legend(ax.get_lines(),[r"LFI ($\delta=0.01$)",r"LFI ($\delta=0.1$)",r"LFI ($\delta=1$)"],
         fancybox=True, shadow=True,fontsize=15,bbox_to_anchor=(0.72,0.9))

ax_inset.set_title("CDF")
ax_inset.spines['top'].set_visible(False)
ax_inset.spines['right'].set_visible(False)
ax.set_xlabel(r"$\phi($"+"LocalFlowImprove) / "+r"$\phi($"+"MQI)",fontsize=15)
#ax.set_title("Conductance improvement",fontsize=15)
ax.set_ylabel("Probability density",fontsize=15)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.tick_params(axis='y', which='both', length=5,width=2)
ax.tick_params(axis='x', which='both', length=5,width=2)
for tick in ax.xaxis.get_major_ticks():
    tick.label.set_fontsize(15)
for tick in ax.yaxis.get_major_ticks():
    tick.label.set_fontsize(15)

plt.show()

f.savefig("cluster_improvement_MQI_BFS.pdf",format='pdf',bbox_inches='tight')

# +
import multiprocessing as mp

def clutser_improvement(g,ratio,rholist,nprocs):
    records = []
    def wrapper(q_in,q_out):
        while True:
            seed = q_in.get()
            if seed is None:
                break
            gamma = 0.01/0.99
            alpha = 1.0-1.0/(1.0+gamma)
            for rho in rholist:
                l1reg_output = spectral_clustering(g,[seed],rho=rho,alpha=alpha,method="l1reg-rand",cpp=False)
                mqi_output = flow_clustering(g,l1reg_output[0],method="mqi_weighted")
                sl_output1 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=0.01)
                sl_output2 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=0.1)
                sl_output3 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=1)
                print(rho,len(l1reg_output[0]),len(mqi_output[0]),len(sl_output1[0]),len(sl_output2[0]),len(sl_output3[0]))
                q_out.put((rho,"node",l1reg_output[1],mqi_output[1],sl_output1[1],sl_output2[1],sl_output3[1]))
            for rho in rholist:
                R = [seed]
                R.extend(g.neighbors(seed))
                l1reg_output = spectral_clustering(g,R,rho=rho,alpha=alpha,method="l1reg-rand",cpp=False)
                mqi_output = flow_clustering(g,l1reg_output[0],method="mqi_weighted")
                sl_output1 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=0.01)
                sl_output2 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=0.1)
                sl_output3 = flow_clustering(g,l1reg_output[0],method="sl_weighted",delta=1)
                print(rho,len(l1reg_output[0]),len(mqi_output[0]),len(sl_output1[0]),len(sl_output2[0]),len(sl_output3[0]))
                q_out.put((rho,"set",l1reg_output[1],seed))
    n = g._num_vertices
    np.random.seed(seed=123)
    seeds = np.random.choice(range(n),size=int(ratio*n), replace=False)
    q_in,q_out = mp.Queue(),mp.Queue()
    procs = [mp.Process(target=wrapper,args=(q_in,q_out)) for i in range(nprocs)]
    for seed in seeds:
        q_in.put(seed)
    for i in range(nprocs):
        q_in.put(None)
    for p in procs:
        p.start()
    ncounts = 0
    t1 = time.time()
    while ncounts < len(rholist)*len(seeds):
        ncounts += 1
        record = q_out.get()
        print(ncounts,len(rholist)*len(seeds),record[2])
        print(time.time()-t1)
        records.append(record)
    for p in procs:
        p.join()
    return records

#graph = GraphLocal("com-orkut.ungraph.txt")
graph = GraphLocal("../../dataset/lawlor-spectra-k32.edgelist","edgelist")
g = graph.largest_component()
ratio = 0.001
rholist = [1.0e-5,1.0e-6,1.0e-7]
records = clutser_improvement(g,ratio,rholist,40)

# +
# import pickle
# rptr = open("ncp_records8.p","rb")
# records = pickle.load(rptr)
# rptr.close()

improvement = np.array([[i[3]/i[2],i[4]/i[2],i[5]/i[2],i[6]/i[2]] for i in records])

f, ax = plt.subplots(1,1,figsize=(8,4),gridspec_kw={"wspace":0.05})
ax_inset = f.add_axes([0.2,0.6,0.2,0.2])
x_inset = np.array(range(0,101))*0.01

ax_inset.set_xlim(-0.0001,1.02)
ax_inset.set_ylim(-0.0001,1.02)
ax.set_xlim(-0.0001,1)
ax.set_ylim(-0.0001,6)

for i in range(improvement.shape[1]):
    subset = improvement[:,i]
    kde = sm.nonparametric.KDEUnivariate(subset)
    kde.fit(kernel="tri",fft=False,bw=0.03,cut=0,clip=(-1*float("inf"),1))
    ax.plot(kde.support,kde.density,color=colors[i],linewidth=3)
    ax.hist(subset,color=colors[i],bins=100,density=True,alpha=0.2)
    ecdf = ECDF(subset)
    ax_inset.plot(x_inset,ecdf(x_inset),color=colors[i],linewidth=3)

ax_inset.set_title("CDF")
ax_inset.spines['top'].set_visible(False)
ax_inset.spines['right'].set_visible(False)
# ax_inset.spines['left'].set_visible(False)
# ax_inset.spines['bottom'].set_visible(False)
ax.set_xlabel(r"$\phi($"+"Improved) / "+r"$\phi($"+"Seeded PR)",fontsize=15)
#ax.set_title("Conductance improvement",fontsize=15)
ax.set_ylabel("Probability density",fontsize=15)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.tick_params(axis='y', which='both', length=5,width=2)
ax.tick_params(axis='x', which='both', length=5,width=2)
for tick in ax.xaxis.get_major_ticks():
    tick.label.set_fontsize(15)
for tick in ax.yaxis.get_major_ticks():
    tick.label.set_fontsize(15)

f.legend(ax.get_lines(),["MQI",r"LFI ($\delta=0.01$)",r"LFI ($\delta=0.1$)",r"LFI ($\delta=1$)"],
         fancybox=True, shadow=True,fontsize=15,bbox_to_anchor=(0.7,0.95))
f.savefig("cluster_improvement.pdf",format='pdf',bbox_inches='tight')

# +
f, ax = plt.subplots(1,1,figsize=(8,4),gridspec_kw={"wspace":0.05})

ax_inset = f.add_axes([0.2,0.6,0.2,0.2])
x_inset = np.array(range(0,101))*0.01

ax_inset.set_xlim(-0.0001,1.02)
ax_inset.set_ylim(-0.0001,1.02)
ax.set_xlim(-0.0001,1)
ax.set_ylim(-0.0001,6)

for i in range(1,improvement.shape[1]):
    subset = improvement[:,i]
    kde = sm.nonparametric.KDEUnivariate(subset)
    kde.fit(kernel="tri",fft=False,bw=0.03,cut=0,clip=(-1*float("inf"),1))
    ax.plot(kde.support,kde.density,color=colors[i],linewidth=3)
    ax.hist(subset,color=colors[i],bins=100,density=True,alpha=0.2)
    ecdf = ECDF(subset)
    ax_inset.plot(x_inset,ecdf(x_inset),color=colors[i],linewidth=3)

f.legend(ax.get_lines(),[r"LFI ($\delta=0.01$)",r"LFI ($\delta=0.1$)",r"LFI ($\delta=1$)"],
         fancybox=True, shadow=True,fontsize=15,bbox_to_anchor=(0.72,0.9))

ax_inset.set_title("CDF")
ax_inset.spines['top'].set_visible(False)
ax_inset.spines['right'].set_visible(False)
ax.set_xlabel(r"$\phi($"+"LocalFlowImprove) / "+r"$\phi($"+"MQI)",fontsize=15)
#ax.set_title("Conductance improvement",fontsize=15)
ax.set_ylabel("Probability density",fontsize=15)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.tick_params(axis='y', which='both', length=5,width=2)
ax.tick_params(axis='x', which='both', length=5,width=2)
for tick in ax.xaxis.get_major_ticks():
    tick.label.set_fontsize(15)
for tick in ax.yaxis.get_major_ticks():
    tick.label.set_fontsize(15)

plt.show()

f.savefig("cluster_improvement_MQI.pdf",format='pdf',bbox_inches='tight')
# -



StarcoderdataJupyterScriptsDedupFiltered