<jupyter_start><jupyter_text><jupyter_code>pip install cdlib
pip install python-louvain
pip install snap
!pip install leidenalg
!pip install igraph
import leidenalg
import igraph
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import networkx.algorithms.community as nx_comm
from networkx.generators.community import LFR_benchmark_graph
from networkx.algorithms.community import greedy_modularity_communities
from cdlib import algorithms
from community import community_louvain
from time import time
from sklearn.cluster import SpectralClustering
''' Generating Networks '''
n = 250
tau1 = 3
tau2 = 1.5
mu = 0.1
graph1 = LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10)
graph2 = LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10)
graph3 = LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10)
graph4 = LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10)
graph5 = LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10)
graph_list = [graph1, graph2, graph3, graph4, graph5]<jupyter_output><empty_output><jupyter_text>AlgorithmsIn the following blocks I'm going to implement CNM, Louvain, and Leiden algorithms and also I will use walktrap algorithm and surprise community algorithm too. Before each algorithm, I will give a brief intoduction to it.  Louvain AlgorithmThis approach is based on modularity, which tries to maximize the difference between the actual number of edges in a community and the expected number of edges in the community. However optimizing modularity in a network is NP-hard, therefore have to use heuristics. Louvain algorithm is divided into iteratively repeating two phases;1. Local moving of nodes2. Aggregation of the networkIn the first phase, the algorithm assigns a different community to each node of the network. Then for each node, it considered the neighbours and evaluate the gain of modularity by removing the particular node from the current community and placing in the neighbour’s community. The node will be placed in the neighbour’s community if the gain is positive and maximized. The node will remain in the same community if there is no positive gain. This process is applied repeatedly and for all nodes until no further improvement is there.In the second phase, the algorithm builds a new network considering communities found in the first phase as nodes. Once the second phase is completed, the algorithm will reapply the first phase to the resulting network. These steps are repeated until there are no changes in the network and maximum modularity is obtained.One major limitation of the algorithm is the use of storage of the network in the main memory.<jupyter_code>for graph in graph_list:
  total_time = 0
  t0 = time()
  louvain_partition = community_louvain.best_partition(graph)
  # print(louvain_partition)
  modularity1 = community_louvain.modularity(louvain_partition, graph)
  t1 = time()
  print('The modularity Q based on networkx is {}'.format(modularity1))
  print('Louvain takes %f\n\n' %(t1 - t0))<jupyter_output><empty_output><jupyter_text>Clauset-Newman-Moore algorithmThe Clauset-Newman-Moore (CNM) algorithm is a greedy algorithm that is very similar to the Louvain Algorithm. The initialization is the same. Then, instead of moving a single node from one community to another, we combine the pair of communities that maximize the increase in modularity. Also, we do not perform the community aggregation step, and continually combine pairs of communities that maximize the increase in modularity until we can no longer combine communities.<jupyter_code>for graph in graph_list:
  t0 = time()
  c = list(greedy_modularity_communities(graph))
  modularity2 = nx_comm.modularity(graph, c)
  t1 = time()
  print('The modularity Q based on networkx is {}'.format(modularity2))
  print('CNM takes %f\n\n' %(t1 - t0))<jupyter_output><empty_output><jupyter_text>Leiden algorithmGirvan-Newman algorithm relies on the iterative elimination of edges that have the highest number of shortest paths between nodes passing through them. By removing edges from the graph one-by-one, the network breaks down into smaller pieces, so-called communities. The algorithm was introduced by <NAME> and <NAME>.<jupyter_code>for graph in graph_list:
  t0 = time()
  g = igraph.Graph.from_networkx(graph)
  part = leidenalg.find_partition(g, leidenalg.ModularityVertexPartition)
  modularity3 = nx_comm.modularity(graph, list(part))
  t1 = time()
  print('The modularity Q based on networkx is {}'.format(modularity3))
  print('Leiden takes %f\n\n' %(t1 - t0))<jupyter_output><empty_output><jupyter_text>Spectral<jupyter_code>for graph in graph_list:
  t0 = time()
  adjacent_mat = nx.to_numpy_matrix(graph1)
  sc = SpectralClustering(4, affinity='precomputed', n_init=100)
  sc.fit(adjacent_mat)
  lg = list(graph1)
  num = len(set(sc.labels_))
  cluster = []
  for i in range(num):
    cluster.append([])
  for i , val in enumerate(sc.labels_):
    cluster[val].append(lg[i])
  t1 = time()

  print("Modularity score : ",nx_comm.modularity(graph1, cluster))
  print('Spectral takes %f\n\n' %(t1 - t0))<jupyter_output><empty_output><jupyter_text>Drawing our generated networks, Just for fun!<jupyter_code># drawing in circular layout
nx.draw_circular(graph1, with_labels = True)
plt.savefig("circular1.png", dpi=1000)
 
# clearing the current plot
plt.clf()
 
# drawing in random layout
nx.draw_random(graph2, with_labels = True)
plt.savefig("random3.png", dpi=1000)
 
# clearing the current plot
plt.clf()
 
# drawing in spectral layout
nx.draw_spectral(graph3, with_labels = True)
plt.savefig("spectral4.png", dpi=1000)
 
# clearing the current plot
plt.clf()
 
# drawing in spring layout
nx.draw_spring(graph4, with_labels = True)
plt.savefig("spring5.png", dpi=1000)
 
# clearing the current plot
plt.clf()
 
# drawing in shell layout
nx.draw_shell(graph5, with_labels = True)
plt.savefig("shell6.png", dpi=1000)
 
# clearing the current plot
plt.clf()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0794766966475879, 'fraction_numerical': 0.01913327882256746, 'mean_word_length': 5.611891891891892, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 27, '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': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '202243', 'license': 'MIT', 'n_tokens_mistral': 1978, 'n_tokens_neox': 1865, 'n_words': 684, 'path': 'UofT_TakeHomeAssignment.ipynb', 'repo_name': 'RamanEbrahimi/Others', 'size': '6129'}