[Bot]

Salut,
Tout est dans le titre. Je dois faire l’algo de Louvain en Python.
J’ai un code qui ne marche pas pour je ne sais quelle raison (génération avec chat)
J’envoie en réponse a ce message le code

Si jamais vous voyez pour quelle raison ca ne me renvoie pas le bon résultat, ou si vous avez un autre méthode, je suis preneur.
Merci.

——————–
Adamou02 – Envoyé depuis le Discord : Culte du code

Sujet

[Bot]

import random

def louvain(graph):
    # Initialisation
    partitions = {node: i for i, node in enumerate(graph)}
    random.shuffle(list(graph.keys()))
    modularity = compute_modularity(graph, partitions)
    
    # Boucle principale
    while True:
        # Étape 1: optimisation de la modularité locale
        converged = False
        while not converged:
            converged = True
            for node in graph:
                current_community = partitions[node]
                best_community = current_community
                best_delta_modularity = 0
                
                for neighbor in graph[node]:
                    neighbor_community = partitions[neighbor]
                    if neighbor_community == current_community:
                        delta_modularity = compute_delta_modularity(
                            graph, partitions, current_community, neighbor)
                        if delta_modularity > best_delta_modularity:
                            best_delta_modularity = delta_modularity
                            best_community = neighbor_community
                
                if best_community != current_community:
                    partitions[node] = best_community
                    converged = False
                    
            if converged:
                break
        
        # Étape 2: agrégation des communautés locales
        communities = {}
        for node, community in partitions.items():
            if community not in communities:
                communities[community] = set()
            communities[community].add(node)
        
        new_partitions = {node: i for i, nodes in enumerate(communities.values()) for node in nodes}
        new_modularity = compute_modularity(graph, new_partitions)
        if new_modularity - modularity < 1e-10:
            break
        
        partitions = new_partitions
        modularity = new_modularity
    
    return partitions

——————–
Adamou02 – Envoyé depuis le Discord : Culte du code

[Bot]

def compute_modularity(graph, partitions):
    m = len(graph.edges())
    q = 0
    for i, community in enumerate(set(partitions.values())):
        nodes = [node for node, comm in partitions.items() if comm == community]
        subgraph = graph.subgraph(nodes)
        lc = len(subgraph.edges())
        dc = sum(graph.degree(node) for node in nodes)
        q += lc / m - (dc / (2 * m)) ** 2
    return q

def compute_delta_modularity(graph, partitions, current_community, neighbor):
    m = len(graph.edges())
    lc = sum(
        1 for node in graph.neighbors(neighbor)
        if partitions[node] == current_community
    )
    dc = sum(graph.degree(node) for node in graph)
    k_i = graph.degree(neighbor)
    k_i_in = sum(
        graph.degree(node) for node in graph.neighbors(neighbor)
        if partitions[node] == current_community
    )
    delta_modularity = (
        2 * lc / m - 2 * k_i * k_i_in / (2 * m * m) -
        2 * lc / (2 * m) + 2 * k_i * dc / (2 * m * m)
    )
    return delta_modularity

# Construire le graphe directement en Python
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E', 'F'],
    'C': ['A', 'G', 'H'],
    'D': ['A', 'I', 'J'],
    'E': ['B'],
    'F': ['B'],
    'G': ['C'],
    'H': ['C'],
    'I': ['D'],
    'J': ['D']
}

# Exemple d'utilisation de l'algorithme de Louvain
if __name__ == '__main__':
    communities = louvain_algorithm(graph)
    print(communities)

——————–
Adamou02 – Envoyé depuis le Discord : Culte du code

[Auteur]

Réponses