<jupyter_start><jupyter_text>Dendrogram from community detection by Girvan-Newman In this notebook we will show how to use the method `dendrogram_from_girvan_newman.py` to plot a dendrogram from community detection performed by the Girvan-Newman algorithm.The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph. The algorithm removes the "most valuable" edge, traditionally the edge with the highest betweenness centrality, at each step. As the graph breaks down into pieces, the tightly knit community structure is exposed and the result can be depicted as a dendrogram.Usually the `scipy.cluster.hierarchy.dendrogram` function is used to draw dendrograms.It receives in input a matrix which encodes the hierarchical clustering to render as a dendrogram. For many cases it is enough to have this matrix generated by the `scipy.cluster.hierarchy.linkage` function, but not so, for example, in graph community detection.The `dendrogram_from_girvan_newman` module provides functions that generate a matrix of this type (named `agglomerative matrix`) starting from the community reconstruction of a graph, performed with the 'girvan_newman' function  from `networkx.algorithms.community.centrality`. The `agglomerative matrix` is suitable to be taken in input by the `scipy.cluster.hierarchy.dendrogram` function.<jupyter_code>import networkx as nx
import dendrogram_from_girvan_newman as dgn
# 1) Generate a simple network.

# nodes and edges
nodes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
edges = [(0, 1), (0, 10), (0, 11), (1, 3), (3, 2), (3, 4), (3, 5), (4, 2), 
         (4, 5), (5, 2), (5, 6), (5, 7), (5, 8), (8, 9)]

# graph
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

# info
nn = nx.number_of_nodes(G)
ne = nx.number_of_edges(G)
print ('The graph G has:\t %d nodes'%nn)
print ('The graph G has:\t %d edges'%ne)
# 2) Draw the network.
nx.draw_networkx(G)
# 3) Perform community detection using Girvan-Newman.

# create the list of prtitions detected by Girvan-Newman
partitions = dgn.girvan_newman_partitions(G)

# print the list of partitions
for i, part in enumerate(partitions):
    print ('partition number %d:\t'%i, part)
    
print ('\nN.B: number of partitions: %d\t is equal to\t (number of nodes - 1): %d - 1'
      %(len(partitions), nn))
# 4) Create the 'agglomerative matrix' associated to the community detection.

# agglomerative matrix
agglomerative_mat = dgn.agglomerative_matrix(G, partitions)

print ('Agglomerative matrix:\n', agglomerative_mat)
# 5) Use the 'agglomerative matrix' to plot the dendrogram. 
#    To do the plot use 'scipy.cluster.hierarchy.dendrogram'.

from scipy.cluster.hierarchy import dendrogram

# plot dendrogram
dendro = dendrogram(agglomerative_mat)
# 6) Find the 'best partitions' among all the partitions detected by Girvan-Newman.
#    The best partition is selected according to its modularity. 
#    (Using 'networkx.algorithms.community.quality.modularity').

# best_partition, position of best partition in the list 'partitions'
bp_G, idx_bp_G = dgn.girvan_newman_best_partition(G, partitions)

print ('The best community partition of the graph G is:\n\t', bp_G)
print ('\nWhich is the one with index = %d among the partitions in the list "partitions".'
       %(idx_bp_G))
# Plot the dendrogram highlighting the best partition.

# How many communities in the best partition?
n_communities_bp = len(bp_G)
print ('The best partition splits the graph G into %d communities.'%n_communities_bp)

# Distance of the best partition from the ground level
dist_bp = dgn.distance_of_partition(agglomerative_mat, n_communities_bp)
print ('The best partition, which splits the graph G into %d communities, has a distance from the ground level equal to:\t %d'
      %(n_communities_bp, dist_bp))

# Plot the dendrogram highlighting the communities which compose the best partition
dendro_bp = dendrogram(agglomerative_mat, color_threshold=dist_bp)<jupyter_output>The best partition splits the graph G into 3 communities.
The best partition, which splits the graph G into 3 communities, has a distance from the ground level equal to:	 6
{'fraction_non_alphanumeric': 0.08584518929346516, 'fraction_numerical': 0.013262599469496022, 'mean_word_length': 4.9855699855699855, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '303944', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 1369, 'n_tokens_neox': 1277, 'n_words': 519, 'path': 'EXAMPLE_dendrogram_from_girvan_newman.ipynb', 'repo_name': 'FrancescoBonacina/dendrogram_girvan-newman', 'size': '4147'}