<jupyter_start><jupyter_text>Demo of the contribution submitted at LEG workshop at ECML-PKDD 2019This notebook allows to easily test the method introduced in the article:`Detecting Stable Communities in Link Streams at Multiple Temporal Scales`Authors: `<NAME>, <NAME>, <NAME>, <NAME>`  `tnetwork` library installationThe code is built on a custom library, that must be first installed using `pip`.If you're running this code online, you probably need to execute the command in the next cell.The documentation of this library can be found at: http://tnetwork.readthedocs.io/<jupyter_code>!pip install --upgrade git+https://github.com/Yquetzal/tnetwork.git<jupyter_output>Collecting git+https://github.com/Yquetzal/tnetwork.git
  Cloning https://github.com/Yquetzal/tnetwork.git to /tmp/pip-req-build-f_xptghm
  Running command git clone -q https://github.com/Yquetzal/tnetwork.git /tmp/pip-req-build-f_xptghm
Requirement already satisfied, skipping upgrade: numpy in /usr/local/lib/python3.6/dist-packages (from tnetwork==0.1) (1.18.2)
Requirement already satisfied, skipping upgrade: matplotlib in /usr/local/lib/python3.6/dist-packages (from tnetwork==0.1) (3.2.1)
Requirement already satisfied, skipping upgrade: scikit-learn in /usr/local/lib/python3.6/dist-packages (from tnetwork==0.1) (0.22.2.post1)
Requirement already satisfied, skipping upgrade: networkx>=2.4 in /usr/local/lib/python3.6/dist-packages (from tnetwork==0.1) (2.4)
Requirement already satisfied, skipping upgrade: pandas in /usr/local/lib/python3.6/dist-packages (from tnetwork==0.1) (0.25.3)
Requirement already satisfied, skipping upgrade: bokeh in /usr/local/lib/python3.6/dist-packages (from t[...]<jupyter_text>We can now import a set of useful libraries<jupyter_code>import tnetwork as tn
import networkx as nx
import numpy as np
from bokeh.io import show, output_notebook, output_file, reset_output
from bokeh.layouts import row
from tnetwork.DCD.analytics.NMIs import NMI<jupyter_output><empty_output><jupyter_text>We finally import the methods introduced in the article. Note that their code is integrated in the tnetwork library, but also availale as stand-alones on the same git repository as this file<jupyter_code># Our proposed method: Multiple Temporal Scale Stable Community Detection method
from tnetwork.DCD import MSSCD  
#Generator
from tnetwork.DCD.multi_temporal_scale import generate_multi_temporal_scale<jupyter_output><empty_output><jupyter_text>Generate a random graph with multiple temporal scale communities<jupyter_code>T=1000
N= 50
SC=5
#return the generated dynamic graph and the discovered communities
generated_graph,original_coms = generate_multi_temporal_scale(nb_steps=T,nb_nodes=N,nb_com = SC)<jupyter_output><empty_output><jupyter_text>Plot the communities to discoverEach horizontal position corresponds to a node, color lines represent communities* /!\ In the google colab notebook, one cannot open plots in new windows, so we use `output_notebook` and not `output_file`, to display the plots inline. This might slow down the notebook.<jupyter_code>#define the order in which to display nodes
node_order=[str(x) for x in range(N)]
#convert the communities from a format as sequence of snapshots to a format as interval graphs. Each snapshot has a duration of 1.
communities_GT = original_coms.to_DynCommunitiesIG(sn_duration=1)
tn.plot_longitudinal(tn.DynGraphIG(),communities_GT,nodes=node_order,height=400)<jupyter_output>/usr/local/lib/python3.6/dist-packages/numpy/core/numeric.py:2327: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison
  return bool(asarray(a1 == a2).all())<jupyter_text>Detect stable communities using the proposed algorithm<jupyter_code>#we re-state default parameters:
theta_gamma = 1 #minimum temporal scale to consider
theta_q = 0.7 #minimum quality
theta_s = 0.3 #maximum similarity to be considered different
theta_p = 3 #nb consecutive steps to be considered persistant

#persistant_coms is a list of quadruplets (nodes,period,granularity,total_quality_score)
persistant_coms = MSSCD(generated_graph,t_persistance=theta_p,t_quality=theta_q,t_similarity=theta_s)<jupyter_output>------- granularity (gamma):  333  |  # good seeds:  1 # persistent communities found (total):  0
------- granularity (gamma):  166  |  # good seeds:  1 # persistent communities found (total):  0
------- granularity (gamma):  83  |  # good seeds:  9 # persistent communities found (total):  1
------- granularity (gamma):  41  |  # good seeds:  19 # persistent communities found (total):  2
------- granularity (gamma):  20  |  # good seeds:  35 # persistent communities found (total):  4
------- granularity (gamma):  10  |  # good seeds:  43 # persistent communities found (total):  4
------- granularity (gamma):  5  |  # good seeds:  41 # persistent communities found (total):  5
------- granularity (gamma):  2  |  # good seeds:  28 # persistent communities found (total):  5<jupyter_text>Plot communities found, to compare them visuallyWe first convert found stable communities in the appropriate dynamic community format. We use a function allowing to filter communities, that we will use also later for real communities<jupyter_code>def convert_stable_communities(persistant_coms,nb_coms=None,duration_min=0,duration_max=10000000):
    visu_blocks = tn.DynCommunitiesIG()
    if nb_coms==None:
        nb_coms = len(persistant_coms)
    for nodes,period,current_granularity,score in persistant_coms[:nb_coms]:
        if period.duration()>duration_min and period.duration()<duration_max:
            #we give a unique name to each community, since colors are attributed according to community names
            name = str(period.start()).zfill(5)+","+str(nodes)+","+str(current_granularity)
            visu_blocks.add_affiliation(nodes,name,period)
    return visu_blocks<jupyter_output><empty_output><jupyter_text>We can now plot found communities, using the same function as previously<jupyter_code>found_stable_communities = convert_stable_communities(persistant_coms)
tn.plot_longitudinal(tn.DynGraphIG(),found_stable_communities,nodes=node_order,height=400)<jupyter_output>/usr/local/lib/python3.6/dist-packages/numpy/core/numeric.py:2327: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison
  return bool(asarray(a1 == a2).all())<jupyter_text>Compute NMI at each stepWe compute the NMI between the plnated communities and: i) our communities ii) communities found by another dynamic community detection algorithm (`Tracking the evolution of communities in dynamic social networks`, `Greene et al. 2010`)<jupyter_code>#detect communities according to the other solution. We first aggregate the graph at the desired granularity

#aggregate the graph at the desired granularity
granularity = 13
aggregated = generated_graph.aggregate_sliding_window(granularity)

#compute communities
baseline_communities = tn.DCD.iterative_match(aggregated).to_DynCommunitiesIG(sn_duration=granularity)
NMIs_found = []
NMI_baseline = []
for t in range(T):
    g = generated_graph.snapshots(t)
    #get the community structure at that step
    GT_com_t = list(communities_GT.communities(t).values())
    
    #we compute NMI only when there are communities 
    #(actually favorizing the baseline, that find communities even when there aren't)
    if len(GT_com_t)>0: 
        found_com_t = list(found_stable_communities.communities(t).values())
        baseline_com_t = list(baseline_communities.communities(t).values())

        #compute NMIs
        nodes_at_t = g.nodes
        NMIs_found.append( NMI(GT_com_t,found_com_t,allNodes=nodes_at_t))
        NMI_baseline.append(NMI(GT_com_t,baseline_com_t,allNodes=nodes_at_t))<jupyter_output><empty_output><jupyter_text>Compute NMIs<jupyter_code>print("NMI for cumulated: ",np.average(NMI_baseline))
print("NMI for proposed solution: ",np.average(NMIs_found))<jupyter_output>NMI for cumulated:  0.25394287121533343
NMI for proposed solution:  0.5910295550689371<jupyter_text>Real Network Analysis (SocioPatterns)  Loading the datasetThe studied dataset is included into the tnetwork library<jupyter_code>primary_school = tn.DynGraphSN.graph_socioPatterns_Primary_School()
classes = tn.utils.community_utils.read_socioPatterns_Primary_School_com()<jupyter_output><empty_output><jupyter_text>CleaningWe start by removing nodes not belonging to chosen classes<jupyter_code>node_activity = {k:len(p) for k,p in primary_school.node_presence().items()}
to_remove={n for n,v in node_activity.items() if classes[n] not in {"1B","2B","3B","5B"}}
results = primary_school.apply_nx_function(nx.Graph.remove_nodes_from,nodes=to_remove)<jupyter_output><empty_output><jupyter_text>We also defined an ordering of nodes, based on classes<jupyter_code>ordered_nodes = sorted([(n,cl) for n,cl in classes.items()],key=lambda x:x[1])
ordered_nodes = [x[0] for x in ordered_nodes if not x[0] in to_remove]<jupyter_output><empty_output><jupyter_text>We can now compute stable communities. We let the default parameters, but for the granularity limit, since 20s is the rate at which data are collected for this dataset. Note that in the dataset, dates of interaction is represented as timestamps,therefore in term of number of seconds since origin.<jupyter_code>persistant_coms_school = MSSCD(primary_school,t_granularity=20)<jupyter_output>------- granularity (gamma):  38966  |  # good seeds:  0 # persistent communities found (total):  0
------- granularity (gamma):  19483  |  # good seeds:  13 # persistent communities found (total):  0
------- granularity (gamma):  9741  |  # good seeds:  29 # persistent communities found (total):  1
------- granularity (gamma):  4870  |  # good seeds:  54 # persistent communities found (total):  3
------- granularity (gamma):  2435  |  # good seeds:  96 # persistent communities found (total):  6
------- granularity (gamma):  1217  |  # good seeds:  180 # persistent communities found (total):  8
------- granularity (gamma):  608  |  # good seeds:  325 # persistent communities found (total):  19
------- granularity (gamma):  304  |  # good seeds:  569 # persistent communities found (total):  31
------- granularity (gamma):  152  |  # good seeds:  932 # persistent communities found (total):  50
------- granularity (gamma):  76  |  # good seeds:  1419 # persistent communities found (total)[...]<jupyter_text>Plotting the found communities We start by plotting communities of duration more than 2 hoursNote that unlike in the article, here, we do not filter on a single day. One can filter using the `slice` function of class `tn.DynGraphIG`. Alternatively, interactive tools allow to zoom in the figure<jupyter_code>com_to_plot = convert_stable_communities(persistant_coms_school,duration_min=60*60*2)
tn.plot_longitudinal(tn.DynGraphIG(),com_to_plot,height=400,to_datetime=True,nodes=ordered_nodes)<jupyter_output>/usr/local/lib/python3.6/dist-packages/numpy/core/numeric.py:2327: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison
  return bool(asarray(a1 == a2).all())<jupyter_text>Then communities of less than half an hour<jupyter_code>com_to_plot = convert_stable_communities(persistant_coms_school,duration_max=60*30)
#com_to_plot = com_to_plot.slice(1254386420,1254410770)
tn.plot_longitudinal(tn.DynGraphIG(),com_to_plot,height=400,to_datetime=True,nodes=ordered_nodes)<jupyter_output>/usr/local/lib/python3.6/dist-packages/numpy/core/numeric.py:2327: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison
  return bool(asarray(a1 == a2).all())<jupyter_text>Finally, remaining communities<jupyter_code>com_to_plot = convert_stable_communities(persistant_coms_school,duration_min=60*30,duration_max=60*60*2)
#com_to_plot = com_to_plot.slice(1254386420,1254410770)
tn.plot_longitudinal(tn.DynGraphIG(),com_to_plot,height=400,to_datetime=True,nodes=ordered_nodes)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09925558312655088, 'fraction_numerical': 0.028205128205128206, 'mean_word_length': 5.750977107761027, 'pattern_counts': {'":': 0, '<': 66, '<?xml version=': 0, '>': 68, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '179992', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 3926, 'n_tokens_neox': 3655, 'n_words': 1062, 'path': 'simple_demo.ipynb', 'repo_name': 'Yquetzal/ECML_PKDD_2019', 'size': '12118'}