<jupyter_start><jupyter_text>Hungarian mappingIf we have partitions over time, how do we map the clusters in consecutive time frames?<jupyter_code>import pandas as pd
from nwtools import common, communities<jupyter_output><empty_output><jupyter_text>Prepare example dataset<jupyter_code>unmatched_labels = pd.read_csv('unmatched_labels_per_year.csv', index_col='Id')
years = sorted(unmatched_labels.keys())
cluster_sets_per_year = {}
for year in unmatched_labels.columns:
    cluster_sets_per_year[year] = {}
    for cl in unmatched_labels[year].dropna().unique():
        cluster_sets_per_year[year][cl] = list(unmatched_labels[year][unmatched_labels[year]==cl].index)
cluster_list = []
for year in years:
    s = unmatched_labels[year].dropna().reset_index()
    cluster_list.append(s.groupby(year)['Id'].apply(set).to_dict())
## Algorithm
import itertools
import numpy as np

def jaccard(s1, s2):
    s1 = set(s1)
    s2 = set(s2)
    intersect = len(s1.intersection(s2))
    union = len(s1.union(s2))
    if union==0:
        return np.NaN
    return intersect/union
def jaccard_crosstab(part1, part2, keys1, keys2):
    sim = np.zeros((len(part1), len(part2)))
    for (i, c1), (j, c2) in itertools.product(enumerate(keys1), enumerate(keys2)):
        sim[i, j] = jaccard(part1[c1], part2[c2])
    return sim
from scipy.optimize import linear_sum_assignment
def get_mapping(ctab, row_labels, col_labels):
    if ctab.shape[0] > ctab.shape[1]:
        raise Exception('Rows should be fewer than columns')
        
    # Use the Hungarian algorithm
    row_ind, col_ind = linear_sum_assignment(- ctab)
    mapXtoY = {row_labels[r]: col_labels[c] for r, c in zip(row_ind, col_ind)}
    return(mapXtoY)
import string
def map_labels_over_time(labels_list, jaccard=True, min_overlap=0.1, character_labels=True):
    if character_labels:
        new_labels = list(string.ascii_lowercase + string.ascii_uppercase)
    else:
        max_nr_of_labels = np.sum([len(s) for s in labels_list])
        new_labels = list(range(max_nr_of_labels))
    max_new_label = 0
    
    mappings = []

    part1 = None
    for t in range(len(labels_list)):
        part2 = labels_list[t]
        if part1 is None:
            m = {l: new_labels[i] for (i,l) in enumerate(part2.keys())}
            max_new_label = len(part2)
        else:
            col_labels = sorted(part1.keys()) 
            row_labels = sorted(part2.keys()) 

            ctab = jaccard_crosstab(part2, part1, row_labels, col_labels)

            # Add dummy columns
            ctab2 = np.hstack((ctab, np.ones((len(part2), len(part2)))*min_overlap))
            col_labels = col_labels + new_labels[max_new_label:max_new_label+len(part2)]
            m = get_mapping(ctab2, row_labels, col_labels)
            max_new_label = new_labels.index(max(m.values()))+1
        mappings.append(m)
        part1 = {m[c]: part2[c] for c in part2}
    return mappings
years = sorted(cluster_sets_per_year.keys())
labels_list = [cluster_sets_per_year[y] for y in years]
mappings_list = communities.map_labels_over_time(labels_list, jaccard=True, min_overlap=0.1, character_labels=True)
mappings_list = communities.map_labels_over_time(cluster_list, jaccard=True, min_overlap=0.1, character_labels=True)
mappings_list
from IPython.display import display
import string

min_overlap = 0.1
new_labels = list(string.ascii_lowercase + string.ascii_uppercase)
max_new_label = 0

years = sorted(cluster_sets_per_year.keys())
mappings = {}

part1 = None
for year in years:
    print(year)
    part2 = cluster_sets_per_year[year]
    if part1 is None:
        m = {l: new_labels[i] for (i,l) in enumerate(part2.keys())}
        max_new_label = len(part2)
    else:
        col_labels = sorted(part1.keys()) 
        row_labels = sorted(part2.keys()) 
        
        ctab = jaccard_crosstab(part2, part1, row_labels, col_labels)
        
        # Add dummy columns
        ctab2 = np.hstack((ctab, np.ones((len(part2), len(part2)))*min_overlap))
        col_labels = col_labels + new_labels[max_new_label:max_new_label+len(part2)]
        display(pd.DataFrame(ctab2, index=row_labels, columns=col_labels).style.format("{:.2}").background_gradient(low=0, high=1, axis=1))
        m = get_mapping(ctab2, row_labels, col_labels)
        max_new_label = new_labels.index(max(m.values()))+1
    mappings[year] = m
    print(m)
    part1 = {m[c]: part2[c] for c in part2}<jupyter_output>1995
{3.0: 'a', 4.0: 'b', 5.0: 'c', 6.0: 'd', 7.0: 'e', 8.0: 'f'}
1996<jupyter_text>Inspect results<jupyter_code>for year in sorted(years):
    m = mappings[year]
    unmatched_labels['mapped_{}'.format(year)] = [m.get(c, None) for c in unmatched_labels[year]]
mapped_columns = ['mapped_{}'.format(year) for year in years]
community_labels = set(unmatched_labels[mapped_columns].values.flatten())
community_labels.remove(None)
community_labels = sorted(community_labels)
print(community_labels)
unmatched_labels.loc['DE',]
community_labels

for comm in sorted(community_labels):
    print('Community {}'.format(comm))
    for i, year in enumerate(years):
        df_sub = unmatched_labels[unmatched_labels[mapped_columns[i]]==comm]
        if len(df_sub) > 0:
            print(year, list(df_sub.index))<jupyter_output>Community a
1995 ['AE', 'BE', 'CH', 'DK', 'EG', 'FR', 'IL', 'LU', 'MA', 'MT', 'NL', 'NO', 'SA', 'SE', 'ZW']
1996 ['AR', 'BE', 'BI', 'CM', 'CY', 'DK', 'DZ', 'ES', 'FR', 'IE', 'KE', 'LU', 'MA', 'NL', 'RW', 'SE', 'TN']
1997 ['AR', 'BE', 'CM', 'DK', 'ES', 'IE', 'KE', 'LB', 'LU', 'NL', 'PE', 'RW', 'SE', 'SN', 'TN']
1998 ['AR', 'BE', 'DK', 'ES', 'FR', 'IE', 'KE', 'LB', 'LU', 'MA', 'MU', 'NL', 'SE', 'TG', 'TN']
1999 ['BE', 'CI', 'DZ', 'FR', 'LB', 'LU', 'MA', 'TN']
2000 ['DZ', 'FR', 'LY', 'MA', 'TN']
2001 ['CH', 'DZ', 'FR', 'LY', 'MA', 'TN', 'UY']
Community b
1995 ['AU', 'BN', 'CL', 'FJ', 'HK', 'ID', 'IE', 'KR', 'MY', 'NZ', 'PG', 'PH', 'SG', 'TH', 'TW', 'ZA']
1996 ['AE', 'CN', 'HK', 'ID', 'IR', 'JP', 'KR', 'MY', 'PH', 'SA', 'SG', 'TH', 'TW', 'VN']
1997 ['AE', 'AU', 'BN', 'CN', 'FJ', 'HK', 'ID', 'IR', 'JP', 'KR', 'MY', 'NZ', 'PG', 'PH', 'SA', 'SG', 'TH', 'TW', 'VN']
1998 ['AE', 'AU', 'BN', 'CN', 'FJ', 'HK', 'ID', 'IR', 'JP', 'KR', 'MY', 'NZ', 'PE', 'PG', 'PH', 'SA', 'SG', 'TH', 'TW', 'VN']
1999[...]
{'fraction_non_alphanumeric': 0.17958987504005128, 'fraction_numerical': 0.023550144184556233, 'mean_word_length': 4.176616915422885, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 13, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '349314', 'license': 'Apache-2.0', 'n_tokens_mistral': 2488, 'n_tokens_neox': 2357, 'n_words': 536, 'path': 'notebooks/HungarianMapping.ipynb', 'repo_name': 'PhD-Dafne/exploration', 'size': '6242'}