<jupyter_start><jupyter_text>Import required packages<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection
from collections import Counter
import networkx as nx
import community
from itertools import permutations 
import matplotlib.ticker as mtick
import matplotlib as mpl
import matplotlib.cm as cm
import pandas as pd
from sklearn.decomposition import TruncatedSVD

import sys
sys.path.append("../../../LocalGraphClustering/")
import localgraphclustering as lgc<jupyter_output><empty_output><jupyter_text>Load graph and global embedding coordinates<jupyter_code>"""
We refer readers to "Lawlor, Budavári, and Mahoney (2016)" to obtain the graph 
and the corresponding global coordinates.
"""

G = lgc.GraphLocal("galaxy.edgelist","edgelist")
df = pd.read_table("galaxy.coords",header=None)
coords = df[[0,1]].values
x,y = -1*coords[:,0],-1*coords[:,1]
x *= 4
y *= 10<jupyter_output><empty_output><jupyter_text>Compute arrows in the direction flow figure  Sample centers<jupyter_code>buckets = defaultdict(list)
x_step_length,y_step_length = 0.0001,0.0001
min_x,min_y = np.min(x),np.min(y)
for i in range(len(coords)):
    buckets[(int((x[i]-min_x)/x_step_length),int((y[i]-min_y)/y_step_length))].append(i)

center_indices = []

for key in buckets.keys():
    idx = buckets[key][0]
    center_indices.append(idx)<jupyter_output><empty_output><jupyter_text>Expand each center to a set and run SimpleLocal or l1reg PageRank<jupyter_code>"""
arrow_tail_x,arrow_tail_y - the location of arrow tails
flow_arrow_head_x,flow_arrow_head_y - the location of arrow heads from SimpleLocal
spectral_arrow_head_x,spectral_arrow_head_y - the location of arrow heads from l1reg PageRank
"""

gnn,arrow_tail_x,arrow_tail_y = [],[],[]
flow_arrow_head_x,flow_arrow_head_y,spectral_arrow_head_x,spectral_arrow_head_y = [],[],[],[]
for center_id in center_indices:
    radius_curr = 0.0005
    neighs = []
    for i in range(G._num_vertices):
        if np.sqrt((x[i]-x[center_id])**2+(y[i]-y[center_id])**2) < radius_curr:
            neighs.append(i)
    while (len(neighs) < 20 or len(neighs) > 10000) and radius_curr < 0.001:
        if len(neighs) < 20:
            radius_curr *= 1.1
        else:
            radius_curr /= 1.1
        neighs = []
        for i in range(G._num_vertices):
            if np.sqrt((x[i]-x[center_id])**2+(y[i]-y[center_id])**2) < radius_curr:
                neighs.append(i)
    if len(neighs) >= 20 and len(neighs) <= 10000:
        arrow_tail_x.append(x[center_id])
        arrow_tail_y.append(y[center_id])
        gnn.append(neighs)

for seeds in gnn:
    if len(seeds) > 1000:
        delta = 0.05
    else:
        delta = 0.005
    flow_output = lgc.flow_clustering(G,seeds,method="sl_weighted",delta=delta)[0]
    flow_arrow_head_x.append(np.mean(x[flow_output]))
    flow_arrow_head_y.append(np.mean(y[flow_output]))
    spectral_output = lgc.spectral_clustering(G,seeds,method="l1reg-rand",iterations=int(1.0e6))[0]
    spectral_arrow_head_x.append(np.mean(x[spectral_output]))
    spectral_arrow_head_y.append(np.mean(y[spectral_output]))<jupyter_output><empty_output><jupyter_text>Compute local embedding  Select a region of interest<jupyter_code>roi_indices = np.nonzero(x>0.0015)[0]<jupyter_output><empty_output><jupyter_text>Repeatedly run SimpleLocal or l1reg PageRank on random sets inside this region<jupyter_code>M_flow = np.zeros((G._num_vertices,500))
M_spectral = np.zeros((G._num_vertices,500))

for trial_id in range(500):
    np.random.seed(trial_id)
    selected_seed = np.random.choice(roi_indices,1)[0]
    max_radius = 0.0001
    min_radius = 0.0
    iters = 0
    while True:
        iters += 1
        neighs = []
        radius_curr = (min_radius+max_radius)/2
        for i in range(G._num_vertices):
            if np.sqrt((x[i]-x[selected_seed])**2+(y[i]-y[selected_seed])**2) < radius_curr:
                neighs.append(i)
        if len(neighs) > 40000:
            max_radius = radius_curr
        elif len(neighs) < 5000:
            min_radius = radius_curr
        else:
            break
        if iters > 100:
            min_radius = 0.0
            max_radius = 0.0004
            iters = 0
    flow_output = lgc.flow_clustering(G,neighs,method="sl_weighted",delta=0.1)[0]
    M_flow[flow_output,trial_id] = 1
    indices,vals = lgc.approximate_PageRank(G,neighs,method="l1reg-rand",alpha=0.001,iterations=int(2e6),rho=1.0e-8)
    M_spectral[indices,trial_id] = vals<jupyter_output><empty_output><jupyter_text>Perform SVD to obtain the local embeddings<jupyter_code>"""
local_coords_flow - local embeddings from SimpleLocal
local_coords_sepctral - local embeddings from l1reg PageRank
"""

svd = TruncatedSVD(n_components=2, random_state=42,n_iter=40)

Mhat = np.hstack([M_flow,np.array([400*x,400*y]).T])
svd.fit(Mhat)
local_coords_flow = svd.transform(Mhat)

Mhat = np.hstack([M_spectral,np.array([0.00002*x,0.00002*y]).T])
svd.fit(Mhat)
local_coords_spectral = svd.transform(Mhat)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12594208647362157, 'fraction_numerical': 0.032526775089250295, 'mean_word_length': 4.353503184713376, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '423844', 'license': 'MIT', 'n_tokens_mistral': 1987, 'n_tokens_neox': 1855, 'n_words': 331, 'path': 'figures/flow_embedding/local_embedding.ipynb', 'repo_name': 'dgleich/flowpaper-code', 'size': '5042'}