<jupyter_start><jupyter_text>Tutorial on Optimized Normalized Cut of an Undirected Graph GReference:[1] <NAME> and <NAME>.*Normalized Cuts and Image Segmentation*.<jupyter_code>import sys
sys.path.insert(0,'/home/elizabeth/Desktop/GIT/Optimized_Ncut_Directed_and_Undirected/src')

from Optimized_normalised_cut_undirected import *
from vizualize_nx import *<jupyter_output><empty_output><jupyter_text>First, lets build a networkx graph to play with. Please note that this code will run with directed graphs but the results may not be ideal. There is a seperate notbook and .py file for directed graphs.<jupyter_code>G = nx.Graph()
E = [(1,3), (1,2), (3,5), (5,1), (4,7), (6,7), (4,6), (4, 2), (7,8), (8,6), (8,5), (8,9), (9,10), (9,11), (9,12), (11,12), (10,11)]
w = [.5, 1, .6, 1, .7, .5, .5, 1, .5, .2, 1, 1, .3, .5, .9, .2, .1]

for e in range(len(E)):
    s,t = E[e]
    G.add_edge(s,t, weight = w[e])

view_pydot(G, 'weight')<jupyter_output><empty_output><jupyter_text>Now we set a few parameters, if edges are weights then set data to be the edge attribute key for the weight. If this is not specified, then edge weights are automatically set as 1. Similarly, the nodelist is just the set of nodes in G you are trying to find an optimum partition for. Reading results is easier if the nodes are orders, but this is not required so if it not specified then the nodelist is automatically set to be G.nodes().<jupyter_code>data = 'weight'
nodelist = sorted(G.nodes())
nodelist<jupyter_output><empty_output><jupyter_text>Now we look at the weight matrix W and degree matrix D. Notice the W(i,j) entry is the weight of edge i -- j, and the D(i,i) entry is the sum of weights from all edges of node i.<jupyter_code>W = sym_weight_matrix(G, nodelist, data)
W
D = sym_weighted_degree_matrix(G, nodelist, data)
D<jupyter_output><empty_output><jupyter_text>Now we compute the the normalised Laplacian L. i.e., nL = D^(-1/2)(D-W)D^(-1/2) = 1-D^(-1/2)WD^(-1/2). See reference [1] or code for more details. Then we can find the second smallest eigenvector of L and use it to partition the G.<jupyter_code>L = normalized_Laplacian(D, W)
ssV = second_smallest_eigval_vec(L)
ssV<jupyter_output><empty_output><jupyter_text>Of course, all of this can be done with a single function, showing that the partition for the above graph has [1, 2, 3, 4, 5, 6, 7] in one group and [8, 9, 10, 11, 12]. Notice this partition should minimize the normalized cut, which is also returned here as 0.349.<jupyter_code>v2, A, B, Ncut = optimized_normalized_cut(G, nodelist, data)
A, B, Ncut<jupyter_output><empty_output><jupyter_text>We can then partition G further just by restricting the nodeset, a visual of the partitions is also shown.<jupyter_code>nodelist = A
v2, A1, B1, Ncut = optimized_normalized_cut(G, nodelist, data)
print('Three cluster of G are:', B, A1, B1)
color = {}
for i in G:
    if i in B:
        color[i] = 'red'
    if i in A1:
        color[i] = 'blue'
    if i in B1:
        color[i] = 'green'
nx.set_node_attributes(G, color, 'color')

view_pydot(G, 'weight')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12366461638070574, 'fraction_numerical': 0.031725477500809326, 'mean_word_length': 4.764925373134329, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '626017', 'license': 'MIT', 'n_tokens_mistral': 1175, 'n_tokens_neox': 1112, 'n_words': 406, 'path': 'notebooks/Optimied_Normalized_Cut_Undirected.ipynb', 'repo_name': 'Eandreas1857/Optimized_Ncut_Directed_and_Undirected', 'size': '3101'}