Le clustering est une méthode d'analyse de données simple qui permet d'obtenir facilement des résultats utiles. Non seulement les données qui ont à l'origine une structure de réseau, mais aussi les données qui n'ont pas de structure de réseau peuvent être mises en réseau et regroupées en définissant une fonction de distance. Cette entrée explique comment effectuer le clustering et visualiser les résultats.
Qu'est-ce qu'une structure de réseau en premier lieu? Généralement, ce sont des données composées de nœuds et d'arêtes. Les bords peuvent ou non être directionnels Un graphe avec une direction est appelé un graphe orienté, et un graphe sans direction est appelé un graphe non orienté. Certaines arêtes ont des poids et d'autres pas, et certaines sont appelées graphiques pondérés.
Pour diviser un ensemble de données en plusieurs groupes (sous-ensembles). Divisez chaque sous-ensemble afin qu'ils aient des caractéristiques communes Dans l'analyse de réseau, elle est parfois appelée détection de communauté. Lors de l'analyse des données, la méthode de calcul de chaque relation, de mise en réseau, de regroupement et de visualisation en tant que groupe est souvent utilisée pour comprendre la structure des données. C'est une méthode utile qui facilite l'obtention d'informations.
L'algorithme introduit cette fois est un algorithme qui vise à effectuer une division qui maximise la modularité du réseau. La modularité est un indicateur de la densité du réseau par rapport à un réseau aléatoire. Dans un article comparatif de 2010, il a reçu la meilleure évaluation en matière d'extraction de communautés à partir de réseaux (http://arxiv.org/abs/0906.0612).
Un algorithme de clustering bien connu est K-means. Puisque K-means reflète la proximité de chaque nœud, on peut dire que c'est un algorithme qui ne considère que la connexion de premier ordre. L'algorithme introduit cette fois est pour le clustering du réseau. La différence avec K-means
C'est le but.
Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Renaud Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008(10)
À partir du Bitbucket suivant
https://bitbucket.org/taynaud/python-louvain
Visualisez un ensemble de données typique d'un réseau social appelé karate_club.
karate_community.py
import community
import networkx as nx
import matplotlib.pyplot as plt
G = nx.karate_club_graph()
partition = community.best_partition(G)
size = float(len(set(partition.values())))
pos = nx.spring_layout(G)
count = 0.
for com in set(partition.values()):
count += 1.
list_nodes = [nodes for nodes in partition.keys() if partition[nodes] == com]
nx.draw_networkx_nodes(G, pos, list_nodes, node_size=20, node_color = str(count/size) )
plt.show()
Comme mentionné ci-dessus, il est possible de dessiner un graphe uniquement avec Python, Lorsque le réseau devient volumineux, il est souvent pratique de pouvoir effectuer des opérations interactives en dessinant, par exemple en n'utilisant que le plus grand graphique connecté ou en effaçant les arêtes en dessous d'un certain poids. Il existe plusieurs outils de visualisation de graphes, mais cette fois, nous présenterons comment refléter les résultats du clustering dans l'outil de visualisation en utilisant CytoScape comme exemple.
La bibliothèque introduite cette fois est exprimée sur la base de NetworkX. Le réseau représenté par NetworkX peut être écrit dans un format de données pouvant être lié à divers logiciels de visualisation.
Écrivons-le au format GraphML cette fois
Les nœuds peuvent avoir diverses informations d'attribut. Il peut être donné en passant un dict avec l'ID de nœud comme clé. Cela vous permet de conserver des données sur la façon dont chaque nœud est mis en cluster. Exportez-le au format GML.
import community
import networkx as nx
G = nx.karate_club_graph()
partition = community.best_partition(G)
labels = dict([(i, str(i)) for i in xrange(nx.number_of_nodes(G))])
nx.set_node_attributes(G, 'label', labels)
nx.set_node_attributes(G, 'community', partition)
nx.write_gml(G, "community.gml")
Spécifiez un fichier à partir d'un fichier réseau dans la boîte de dialogue après le démarrage et lisez-le. (Ou File-> import-> Network-> File)
Je suis sûr que vous n'êtes pas sûr, mais c'est parce que vous n'avez pas spécifié la mise en page. Tout d'abord, spécifions l'algorithme d'affichage. Si vous sélectionnez Layout-> yFiles Layouts-> Organic, l'affichage sera comme suit.
C'était affiché comme ça.
Ensuite, le résultat du regroupement est reflété dans ce graphique. Cette fois, changeons la couleur du nœud en fonction du cluster. Utilisez le menu Style du Panneau de configuration pour modifier la couleur et la taille du graphique. Si le panneau de contrôle n'est pas affiché, affichez-le avec Affichage-> Afficher le panneau de contrôle.
Utilisez la couleur de remplissage pour changer la couleur. Vous pouvez décider dans quelles conditions les paramètres sont attribués sur la carte. Cliquez sur la carte de l'élément que vous souhaitez modifier
Ces éléments sont affichés. Définissez les éléments de données conditionnels dans Column. Les éléments définis dans set_node_attributes peuvent être sélectionnés. Choisissons la communauté
Sélectionnez les conditions dans lesquelles la définition est modifiée dans Type de mappage. Il existe 3 types
--Mappage continu: Rendez la valeur continue et modifiez la taille et la gradation des couleurs en fonction de la taille. --Mappage discret: définissez les valeurs sous forme de valeurs discrètes et définissez les couleurs pour chaque valeur --PassThrough Mapping: la valeur est utilisée telle quelle. Par exemple, si vous spécifiez le rouge, il deviendra rouge.
Cette fois, le nombre de clusters est aussi petit que 4 et la taille de la valeur n'a pas de sens, alors sélectionnez Mappage discret. Lorsque vous le sélectionnez, le menu déroulant suivant apparaîtra, alors sélectionnez et spécifiez la couleur.
Avec ce paramètre, la couleur du premier graphique change comme ceci. J'ai pu visualiser les résultats du clustering.
Dans cette entrée, nous avons présenté le flux de la mise en cluster réseau à la visualisation. Bien que l'analyse de réseau soit relativement simple, c'est une méthode qui permet d'obtenir facilement des résultats intéressants, donc si vous êtes intéressé, essayez-la!
Recommended Posts