[PYTHON] L'analyse de réseau est une structure de lien Web ②

introduction

La structure de liens du Web est un réseau à grande échelle auquel vous pouvez facilement jouer. L'analyse de réseau est une structure de lien sur le web ① Nous analyserons en fait le réseau acquis. Cela peut prendre plus de 3 heures, alors essayez-le avec votre cœur. Le code source etc. est disponible sur Author GitHub.

Aperçu du programme

1. Créez un graphe orienté avec networkx à partir d'une matrice adjacente
2. Jouez avec le rang de page, la centralité et la décomposition des composants de connexion forte
3. Amusant! !! !!

NetworkX Module d'analyse de réseau. --Plusieurs informations peuvent être données au bord du nœud du graphe.

• Vous pouvez facilement effectuer une analyse de réseau telle que la décomposition de composants centraux / fortement liés.
• Belle visualisation.

Site de référence

~~ Je ne pouvais pas me permettre de rassembler les recettes ~~, alors je vais rassembler les sites Web auxquels j'ai fait référence.

Document officiel de NetworkX Qiita: [Python] Résumé de l'utilisation de base de Network X 2.0 PyQ: Théorie des graphes et réseau X [DATUM STUDIO: J'ai essayé de visualiser le réseau national des noms de famille avec networkx](https://datumstudio.jp/blog/networkx%E3%81%A7%E5%85%A8%E5%9B%BD%E5%90% 8D% E5% AD% 97% E3% 83% 8D% E3% 83% 83% E3% 83% 88% E3% 83% AF% E3% 83% BC% E3% 82% AF% E3% 82% 92% E5% 8F% AF% E8% A6% 96% E5% 8C% 96% E3% 81% 97% E3% 81% A6% E3% 81% BF% E3% 81% 9F)

Préparation

import.py

from urllib.request import urlopen
from bs4 import BeautifulSoup

import networkx as nx

from tqdm import tqdm_notebook as tqdm
import numpy as np
from scipy import stats
import pandas as pd
pd.options.display.max_colwidth = 500

import seaborn as sns
import matplotlib.pyplot as plt
%matplotlib inline

import re

L'analyse de réseau est une structure de liens sur le Web ①.

Création de graphes

make_graph.py

G = nx.DiGraph()

for i in tqdm(range(len(adj))):
    for j in range(len(adj)):
        if adj[i][j]==1:
            G.add_edge(i,j)

nx.DiGraph() Créez un graphique orienté.

G.add_edge(i,j) Ajoutez une arête au graphique «G». ~~ Il existe une manière plus intelligente de l'ajouter. Ouaip. ~~

Calcul des caractéristiques graphiques

cal_centrality.py

degree = nx.degree_centrality(G)
print("degree completed")

closeness = nx.closeness_centrality(G)
print("closeness completed")

betweenness = nx.betweenness_centrality(G)
print("betweenness completed")

pagerank = nx.pagerank(G)
print("pagerank completed")

strong_connection = sorted(nx.strongly_connected_components(G), key=lambda x: len(x), reverse=True)
print("strongly　connected　components completed")

nx.degree_centrality(G) Centralité de la commande. La somme des commandes sortantes et entrantes pour chaque nœud. nx.degree_centrality (G) renvoie la valeur du degré de centralité divisée par $ n-1 . ( n $: Nombre de sommets du graphe)

nx.closeness_centrality(G) Centralité de proximité. L'inverse de la longueur de chemin la plus courte moyenne entre chaque nœud et tous les autres nœuds.

nx.betweenness_centrality(G) Centralité de la médiation. Le nombre de fois que la route la plus courte de tous les autres nœuds aux nœuds accessibles passe par chaque nœud.

nx.strongly_connected_components(G) Décomposition de composants fortement liés. sorted(nx.strongly_connected_components(G), key=lambda x: len(x), reverse=True) Ce faisant, un tableau trié par ordre décroissant du nombre de sommets du composant fortement connecté est renvoyé.

Créer DataFrame de pandas

make_df.py

df = pd.DataFrame({"ID": range(len(url_list)), "URL": url_list)

df["category"] = df["URL"].apply(lambda s: s[s.index(":")+3:s.index("/", 8)])

df.loc[df['URL'] ==start_url, 'category'] = "start_page"

df["degree_centrality"] = df["ID"].map(degree)
df["closeness_centrality"] = df["ID"].map(closeness)
df["betweenness_centrality"] = df["ID"].map(betweenness)
df["Pagerank"] = df["ID"].map(pagerank)

df = df.assign(Pagerank_rank=len(df)-stats.mstats.rankdata(df["Pagerank"])+1)
df = df.assign(degree_centrality_rank=len(df)-stats.mstats.rankdata(df["degree_centrality"])+1)
df = df.assign(closeness_centrality_rank=len(df)-stats.mstats.rankdata(df["closeness_centrality"])+1)
df = df.assign(betweenness_centrality_rank=len(df)-stats.mstats.rankdata(df["betweenness_centrality"])+1)

df.to_csv(f"./{fname}.csv")

df["category"] Classez chaque page du réseau par première page. [L'analyse de réseau est une structure de liens sur le Web ①](https://qiita.com/takahiro_hasegawa/items/2d2a979ead0522c112a2#%E3%83%AA%E3%83%B3%E3%82%AF%E6%A7%8B % E9% 80% A0% E8% A7% A3% E6% 9E% 90% E3% 81% AE% E9% 96% A2% E6% 95% B0), et ʻurl_list` est une URL commençant par http. Stockée. Ces URL sont classées par page principale et utilisées comme «catégorie». Utile pour la visualisation.

df.assign(Pagerank_rank=len(df)-stats.mstats.rankdata(df["###"])+1) Ajoutez des classements de diverses centralités en tant que nouvelles colonnes. stats.mstats.rankdata prend le rang de la même valeur que sa valeur moyenne. stats.mstats.rankdata se classe à partir de 0 dans l'ordre croissant. Prenez-en l'ordre inverse et ajoutez l'ordre de la 1ère place au DataFrame.

Fonction de visualisation graphique

draw_graph.py

pos = nx.spring_layout(G)

nx.spring_layout(G) Calculez la position pour tracer correctement le graphique. Si vous ne définissez pas «pos» en dehors de la fonction, un graphique avec une forme différente sera dessiné à chaque fois.

draw_graph.py

def draw_char_graph(G, pos, title, node_type):
    plt.figure(figsize=(15, 15))

    nx.draw_networkx_edges(G,
                           pos=pos,
                           edge_color="gray",
                           edge_cmap=plt.cm.Greys,
                           edge_vmin=-3e4,
                           width=0.3,
                           alpha=0.2,
                           arrows=False)
    
    if node_type=="centrality":
        node1=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="blue",
                                     alpha=0.8,
                                     node_size=[ d["closeness"]*300 for (n,d) in G.nodes(data=True)])

        node2=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="green",
                                     alpha=0.8,
                                     node_size=[ d["degree"]*2000 for (n,d) in G.nodes(data=True)])

        node3=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="yellow",
                                     alpha=0.8,
                                     node_size=[ d["betweenness"]*5000 for (n,d) in G.nodes(data=True)])

        node4=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="red",
                                     alpha=0.8,
                                     node_size=[ d["pagerank"]*10000 for (n,d) in G.nodes(data=True)])
        
        plt.legend([node1, node2, node3,node4], ["closeness", "degree","betweenness","pagerank"],markerscale=1,fontsize=18)
        plt.title(f"centrality: {start_url}\n {nx.number_of_nodes(G)} nodes,{nx.number_of_edges(G)} edges",fontsize=25)
        
    elif node_type=="simple":
        nx.draw_networkx_nodes(G,
                               pos=pos,
                               node_color="blue",
                               node_size=5)
        plt.title(f"{start_url}\n {nx.number_of_nodes(G)} nodes,{nx.number_of_edges(G)} edges",fontsize=25)
        
    elif node_type=="strong_connection":
        nx.draw_networkx_nodes(G,
                               pos=pos,
                               node_color="black",
                               node_size=10)
        
        node1=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="blue",
                                     nodelist=strong_connection[0],
                                     node_size=30)
        
        node2=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="yellow",
                                     nodelist=strong_connection[1],
                                     node_size=30)
        
        node3=nx.draw_networkx_nodes(G,
                                     pos=pos,
                                     node_color="red",
                                     nodelist=strong_connection[2],
                                     node_size=30)
        
        plt.title(f"strongly connected nodes: {title}\n {nx.number_of_nodes(G)} nodes,{nx.number_of_edges(G)} edges",fontsize=25)
        plt.legend([node1, node2, node3], [f"elements: {len(strong_connection[0])} ({round(len(strong_connection[0])/nx.number_of_nodes(G)*100,2)}%)",
                                           f"elements: {len(strong_connection[1])} ({round(len(strong_connection[1])/nx.number_of_nodes(G)*100,2)}%)",
                                           f"elements: {len(strong_connection[2])} ({round(len(strong_connection[2])/nx.number_of_nodes(G)*100,2)}%)"],markerscale=1,fontsize=18)

    plt.axis('off')
    plt.savefig(f"{title}_graph_{node_type}", dpi=300)
    plt.show()

draw_char_graph(G, pos, title, node_type) Une fonction qui dessine un graphique. title Le titre du graphique à dessiner et le nom du fichier à sauvegarder node_type

Visualisation

Nuage de points

visualize.py

sns.pairplot(df.drop("ID", axis=1), hue='category')
plt.savefig(f'{fname}_pairplot.png')

Tout le monde aime la «parcelle de paires».

réseau

visualize.py

draw_char_graph(G, pos, fname, node_type="simple")

visualize.py

draw_char_graph(G, pos, fname, node_type="centrality")

visualize.py

draw_char_graph(G, pos, fname, node_type="strong_connection")

Je ne suis pas sûr car c'est trop grand. S'il s'agit d'un petit réseau, il sera bien dessiné.

Classement de centralité

visualize.py

df_important = df[(df["Pagerank_rank"]<=10) | (df["degree_centrality_rank"]<=10) | (df["closeness_centrality_rank"]<=10) | (df["betweenness_centrality_rank"]<=10)]
df_important = df_important[["URL", "Pagerank_rank", "degree_centrality_rank", "closeness_centrality_rank", "betweenness_centrality_rank"]]

df_important.to_csv(f"./{fname}_important.csv")

C'est marrant! !! !!