Grafo di un sito internet: un esempio in Python

Condividi se ti piace...

Grafo di un sito internet e ranking: un esempio in Python Tutte le tecnologie, anche quelle di uso quotidiano, hanno alla base un modello matematico ed algoritmi di supporto alla loro implementazione e non sono da meno le tecnologie web. Un esempio classico è il modello linguistico utilizzato nella ricerca semantica da Google e l’algoritmo di stemming per il filtraggio delle stopwords.

Un modello molto più ampio che viene utilizzato da molte tecnologie web è quello basato sui Grafi. Avete mai sentito parlare di Knowledge Graph di Google? O di grafo sociale (o rete sociale) riferito ai social network come Facebook e Linkedin?

Modelli basati sulla teoria dei grafi aiutano a stabilire a rigore le varie connessioni che vi sono tra oggetti o soggetti, stabilendone anche un grado di connessione (o un peso, un’importanza) nell’intero contesto in esame.

Google valuta il nostro sito internet facendo anche delle analisi di questo tipo: vede il nostro sito come un grafo e in buona sostanza stabilisce:

quali sono le connessioni interne (i link interni alle nostre pagine) e quali sono quelle che hanno più valore;
quali sono le connessioni con l’esterno e dandoci un punteggio anche in base al ranking dei siti a cui puntiamo (rilevante principalmente per i post nei quali documentiamo con link esterni di qualità)

MA COS’È UN GRAFO?

Un grafo è una struttura matematica discreta le cui proprietà sono definite dalla Teoria dei Grafi. Non è da confondere con il grafico, che non è altro che una rappresentazione grafica di qualcosa, incluso un grafo.

I grafi vengono utilizzati in diverse branche della scienza e della tecnologia, come in biochimica, nello studio delle interazioni in teoria quantistica dei campi, nello studio delle reti informatiche, nello studio delle topologie nei database geografici e, tra le altre infinità numerabili di cose, anche nel web, in particolare nei social network come Facebook e Linkedin e nel modello di Google per il suo motore di ricerca.

GRAFO DI UN SITO: PERCHÉ È IMPORTANTE

Come detto all’inizio dell’articolo, conoscere il grafo del nostro sito ci aiuta a capire come esso è strutturato, ci indica quali sono le pagine con più valore e di conseguenza ci aiuta a capire quali strategie SEO utilizzare. Ad esempio, possiamo scoprire che la pagina “chi sono” è quella che ha più valore nel nostro sito. Cosa facciamo? Cerchiamo di adottare soluzioni che diano più importanza ad un’altra pagina? o sfruttiamo questa? Ma un’altra informazione che può darci la struttura a grafo di un sito internet è la bontà delle connessioni tra le varie pagine interne.

FACCIAMO UN ESEMPIO CON UN’ANALOGIA

Consideriamo tre stazioni ferroviarie: Milano, Bologna, Bari.

La rete ferroviaria che le collega è rappresentata da una linea spezzata: ogni tratto (ogni segmento o arco) unisce due punti, chiamati nodi. Questi nodi non sono altro che le stazioni intermedie, tra cui le stazioni di Milano, Bologna e Bari sono dei nodi.

Bari è un nodo che avrà le sue diramazioni verso tratte regionali e nazionali. Idem Bologna e Milano. Ma le tre stazioni sono importanti in egual misura? Ovviamente la risposta è no!

Bologna è un importante snodo fra tratte nazionali: se da Bari voglio arrivare a Milano devo passare per la stazione di Bologna, che è quindi più importante della stazione di Bari.

Bologna è quindi un nodo più importante rispetto al nodo Bari.

Milano ha un’importanza ancora maggiore perché è uno snodo verso tratte estere.

Per valutare l’importanza di una stazione ci chiediamo quindi:

quali sono gli snodi regionali?
quali gli snodi nazionali?
quali quelli esteri?

Analogamente, la stessa cosa vale per il nostro sito.

Quali sono le connessioni interne del sito? (le connessioni regionali, in analogia con la rete ferroviaria)
Quali sono le connessioni esterne del sito, ossia verso siti esterni? (connessioni nazionali e internazionali)
Quali sono i nodi (siti) interni più importanti?
Quanto sono importanti i nodi (siti) esterni a cui mi collego? Sono tanti?

ANDIAMO NEL DETTAGLIO

Un articolo bellissimo di Enrico Altavilla, spiega come calcolare la distribuzione del PageRank, mostrando come alla base di questa valutazione vi sia la la struttura a grafo di un sito internet. Nell’articolo inoltre viene spiegata l’utilità di questo tipo di analisi, soprattutto a livello SEO, descrivendo una procedura non tanto complessa.

Le procedure di analisi sono complesse e per spiegarne il senso spesso si cerca di semplificare, cosa che farò nel seguito dell’articolo. Tuttavia è una buona base per approfondire il tema in futuro. Lo scopo in questo articolo è mostrare una semplificazione della procedura di Enrico Altavilla tramite un mio codice scritto in linguaggio Python, molto semplificato e che va ottimizzato in alcuni aspetti tecnici e numerici.

Estrarre tutti i link interni ed esterni di un sito
Creare il grafo di un sito: una serie di nodi e archi dove:
- i nodi sono i link del sito
- gli archi sono le connessioni di ogni link interno con tutti gli altri link
Calcolare qualcosa simile al PageRank, chiamato Eigenvector Centrality, per ogni risorsa del sito
Creare una rappresentazione grafica del grafo.

L’analisi andrebbe fatta nel dettaglio, valutando link con tag nofollow, valutazione dei link esterni, ed eventuali filtraggi e calcoli: mi riprometto di riaggiornare l’articolo non appena ne avrò l’occasione.

COSA CI SERVE

Python, scaricabile dal sito ufficiale, o anche da terminale per utenti Linux e MacOSX.
Le librerie numpy, scipy, matplotlib, networkx, da installare seguendo l’ordine che vi ho elencato!
La libreria beautiful soup, meravigliosa per gestire i contenuti di file html (parsing HTML).

IL CODICE IN PYTHON

(il codice completo lo trovi a fine articolo)

Il codice viene eseguito nel modulo principale: main.

def main(home, sitemap, siteType):

    graph, siteLink = getGraph(sitemap, siteType)

def main(home, sitemap, siteType):

graph, siteLink = getGraph(sitemap, siteType)

dove la prima riga esegue il parsing della sitemap, fornendo come risultato un dizionario ed una lista, ossia:

graph, dizionario dove ogni chiave è un url della nostra sitemap e il corrispondente valore è una lista contenente le url collegate ad esso (link interni a cui rimanda).
siteLink, lista di tutti gli url della sitemap

Questa operazione viene effettuata dal modulo getGraph()

def getGraph(sitemap, site='wordpress'):
    """ get a dict from sitemap, to construct nodes and edges """
    
    xml = getChild(sitemap)
    documents = {}
    graph0 = {}
    graph = {}
    siteLink = []

    if site=='wordpress':
        for x in xml.keys():
            for k in xml[x]:
                graph[k] = getLink(k)
                siteLink.append(k)
                print k
    else:
        for k in xml:
            graph[k] = getLink(k)
            siteLink.append(k)
            print k

    return graph, siteLink

def getGraph(sitemap, site='wordpress'):

""" get a dict from sitemap, to construct nodes and edges """

xml = getChild(sitemap)

documents = {}

graph0 = {}

graph = {}

siteLink = []

if site=='wordpress':

for x in xml.keys():

for k in xml[x]:

graph[k] = getLink(k)

siteLink.append(k)

print k

else:

for k in xml:

graph[k] = getLink(k)

siteLink.append(k)

print k

return graph, siteLink

la riga

xml = getChild(sitemap)

1	xml = getChild(sitemap)

esegue un parsing della sitemap fornita. Successivamente per ogni url della sitemap viene effettuato un parsing html (url k) tramite

graph[k] = getLink(k)

1	graph[k] = getLink(k)

sfruttando la liberia beautiful soup (bs4). Le funzioni getChild() e getLink() sono esposte a fine articolo

La funzione fa una distinzione tra le sitemap tipiche fornite dal plugin Yoast WordPresse le sitemap fornite da siti implementati in Joomla.

In particolare una sitemap di Yoast è sviluppata come un albero di file xml:

sitemap_index.xml
- post-sitemap.xml
  - url 1
  - url 2
  - …
- page-sitemap.xml
  - url 3
  - url 4
  - …
- portfolio-sitemap.xml
  - …
- category-sitemap.xml
  - …
- e così via…

Le sitemap fornite dai componenti per Joomla invece sono del tipo:

sitemap.xml
- url 1
- url 2
- url 3
- url 4
- ….

Ritorniamo al modulo main. Dopo aver estratto url e link, passiamo a crearci il grafo del sito. Lo facciamo tramite la libreria networkx, importata con l’abbreviazione nx.

    ....
    # creo il grafo
    G = nx.Graph()
    G.add_nodes_from(generateNodes(graph))
    G.add_edges_from(generateEdges(graph))

....

# creo il grafo

G = nx.Graph()

G.add_nodes_from(generateNodes(graph))

G.add_edges_from(generateEdges(graph))

generateNodes() e generateEdges() sono i moduli tramite i quali vengono estratti i nodi e gli archi secondo il formato richiesto da networkx.

Successivamente ci calcoliamo i valori di Eigenvectors Centrality

    ...
    print 'EIGENVECTORS CENTRALITY'
    ec = nx.eigenvector_centrality(G, max_iter=100)

...

print 'EIGENVECTORS CENTRALITY'

ec = nx.eigenvector_centrality(G, max_iter=100)

quindi scriviamo su file csv sia i valori di Eigenvectors Centrality, sia i gradi di ogni nodo

    fec = open('ec.csv','w')
    for k in ec.keys():
        fec.write(str(k)+';'+str(ec[k])+'\n')
    fec.close

    fdeg = open('nodeDegree.csv', 'w')
    for v in G:
        fdeg.write(str(v)+';'+str(float(G.degree(v)))+'\n' )
    fdeg.close()

fec = open('ec.csv','w')

for k in ec.keys():

fec.write(str(k)+';'+str(ec[k])+'\n')

fec.close

fdeg = open('nodeDegree.csv', 'w')

for v in G:

fdeg.write(str(v)+';'+str(float(G.degree(v)))+'\n' )

fdeg.close()

Infine impostiamo i parametri di plottaggio per ottenere una rappresentazione grafica del grafo del sito in esame, salvandola in alta risoluzione su file pdf

    nomeFig = 'grafo.pdf'
    tipoFig = 'pdf'


    graph_pos=nx.spring_layout(G, iterations=400, scale=1)#, dim=10000)


    print 'GRAPG POS'

    for n in graph_pos:
        graph_pos[n] = graph_pos[n]*100


    nx.draw_networkx_nodes(G,graph_pos,node_size=[float(G.degree(v))*0.3 for v in G], alpha=0.7, node_color=[float(ec[k]) for k in G.nodes(data=False)],with_labels=False)
    nx.draw_networkx_edges(G,graph_pos,width=0.1,alpha=0.5,edge_color='r', arrows=True)
    nx.draw_networkx_labels(G, graph_pos,font_size=0,font_family='sans-serif')

    plt.axis('off')
    plt.savefig(nomeFig, format=tipoFig, dpi='9000', figsize=(32.000, 32.000)) # save as png
    plt.show()

nomeFig = 'grafo.pdf'

tipoFig = 'pdf'

graph_pos=nx.spring_layout(G, iterations=400, scale=1)#, dim=10000)

print 'GRAPG POS'

for n in graph_pos:

graph_pos[n] = graph_pos[n]*100

nx.draw_networkx_nodes(G,graph_pos,node_size=[float(G.degree(v))*0.3 for v in G], alpha=0.7, node_color=[float(ec[k]) for k in G.nodes(data=False)],with_labels=False)

nx.draw_networkx_edges(G,graph_pos,width=0.1,alpha=0.5,edge_color='r', arrows=True)

nx.draw_networkx_labels(G, graph_pos,font_size=0,font_family='sans-serif')

plt.axis('off')

plt.savefig(nomeFig, format=tipoFig, dpi='9000', figsize=(32.000, 32.000)) # save as png

plt.show()

CODICE COMPLETO

NOTA: il codice è molto semplice e l’ho scritto velocemente a titolo di esempio. Tuttavia sono ben accetti suggerimenti!

Lancio del codice (esempio)

python main.py -s http://www.nicolastella.it/sitemap.xml -p http://www.nicolastella.it/ -t wordpress

1	python main.py -s http://www.nicolastella.it/sitemap.xml -p http://www.nicolastella.it/ -t wordpress

File main.py

import urllib2
import bs4
import numpy as np
import requests
from lxml import etree
import networkx as nx
import matplotlib.pyplot as plt
from optparse import OptionContainer, OptionParser, OptionGroup, Option


def getChild(linkXml):
    xmlDict = {}
    sitemapPages = {}

    r = requests.get(linkXml)
    root = etree.fromstring(r.content)

    for sitemap in root:
        children = sitemap.getchildren()
        xmlDict[children[0].text] = []
        if children[0].text[-3:] == 'xml':
            rq = requests.get(children[0].text)
            subXml = etree.fromstring(rq.content)
            for el in subXml:
                pgs = el.getchildren()
                xmlDict[children[0].text].append(pgs[0].text)

    return xmlDict

def getLink(link):
    connections = []
    nodes = []
    nodesName = []
    beautiful = urllib2.urlopen(link).read()
    soup = bs4.BeautifulSoup(beautiful)
    links = soup.findAll('a')
    for l in links:
        ln = l.get('href')
        #cn = l.string
        #connections.append((cn, ln))
        nodes.append(ln)

    return nodes

def generateNodes(graph):

    """ return a list of nodes """
    nodes = graph.keys()
    return nodes

def generateEdges(graph):

    """ return a list of tuples thath represents edges """
    edges = []
    for vertex in graph:
        for neighbour in graph[vertex]:
            if {neighbour, vertex} not in edges:
                edges.append((vertex, neighbour))

    return edges

def getGraph(sitemap, site='wordpress'):
    """ get a dict from sitemap, to construct nodes and edges """
    
    xml = getChild(sitemap)
    documents = {}
    graph0 = {}
    graph = {}
    siteLink = []

    if site=='wordpress':
        for x in xml.keys():
            for k in xml[x]:
                graph[k] = getLink(k)
                siteLink.append(k)
                print k
    else:
        for k in xml:
            graph[k] = getLink(k)
            siteLink.append(k)
            print k
        
    return graph, siteLink

def main(home, sitemap, siteType):

    graph, siteLink = getGraph(sitemap, siteType)

    print 'GRAPH\n\n'
    #preparo i dati

    ## TUTTO
    G = nx.Graph()
    G.add_nodes_from(generateNodes(graph))
    G.add_edges_from(generateEdges(graph))

    #eccentricity = nx.eccentricity(G)
    #pr = nx.pagerank(G)
    #googleMatrix = nx.google_matrix(G)

    #print 'ECCENTRICITY'
    #print eccentricity
    #print 'PAGE RANK'
    #print pr
    #print 'GOOGLE MATRIX'
    #print googleMatrix

    print 'EIGENVECTORS CENTRALITY'
    ec = nx.eigenvector_centrality(G, max_iter=100)

    fec = open('ec.csv','w')
    for k in ec.keys():
        fec.write(str(k)+';'+str(ec[k])+'\n')
    fec.close

    fdeg = open('nodeDegree.csv', 'w')
    for v in G:
        fdeg.write(str(v)+';'+str(float(G.degree(v)))+'\n' )
    fdeg.close()

    nomeFig = 'grafo.pdf'
    tipoFig = 'pdf'

    graph_pos=nx.spring_layout(G, iterations=400, scale=1)#, dim=10000)

    print 'GRAPG POS'

    for n in graph_pos:
        graph_pos[n] = graph_pos[n]*100

    nx.draw_networkx_nodes(G,graph_pos,node_size=[float(G.degree(v))*0.3 for v in G], alpha=0.7, node_color=[float(ec[k]) for k in G.nodes(data=False)],with_labels=False)
    nx.draw_networkx_edges(G,graph_pos,width=0.1,alpha=0.5,edge_color='r', arrows=True)
    nx.draw_networkx_labels(G, graph_pos,font_size=0,font_family='sans-serif')

    plt.axis('off')
    plt.savefig(nomeFig, format=tipoFig, dpi='9000', figsize=(32.000, 32.000)) # save as png
    plt.show()


if __name__ == "__main__":

    home = None
    sitemap = None
    siteType = None
    
    parser = OptionParser(usage="%prog [options]")
    parser.add_option("-s", "--sitemap_url", action="store", dest="sitemap_url", default=None, help="Complete url of sitemap, with http://")
    parser.add_option("-p", "--homepage", action="store", dest="homepage", default=None, help="Complete url of homepage with http://")
    parser.add_option("-t", "--cms_type", action="store", dest="cms_type", default="wordpress", help="CMS Type: joomla or worpress. Default: wordpress")

    (options, args) = parser.parse_args()
    
    if options.sitemap_url == None:
        print 'You must specify a sitemap url'
        exit()
    elif str(options.sitemap_url[-4:]) != '.xml':
        print "You must specify an xml sitemap"
        exit()
    else:
        sitemap = str(options.sitemap_url)

    if str(options.homepage) == None:
        print 'You must specify a url'
        exit()
    else:
        homepage = str(options.homepage)

    if options.cms_type == None:
        print 'You must specify a cms type: wordpress or joomla'
        exit()
    elif str(options.cms_type) not in ['wordpress','joomla']:
        print "You must specify one choice between: wordpress, joomla"
        exit()
    else:
        siteType = str(options.cms_type)

    main(homepage, sitemap, siteType)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

import urllib2

import bs4

import numpy as np

import requests

from lxml import etree

import networkx as nx

import matplotlib.pyplot as plt

from optparse import OptionContainer, OptionParser, OptionGroup, Option

def getChild(linkXml):

xmlDict = {}

sitemapPages = {}

r = requests.get(linkXml)

root = etree.fromstring(r.content)

for sitemap in root:

children = sitemap.getchildren()

xmlDict[children[0].text] = []

if children[0].text[-3:] == 'xml':

rq = requests.get(children[0].text)

subXml = etree.fromstring(rq.content)

for el in subXml:

pgs = el.getchildren()

xmlDict[children[0].text].append(pgs[0].text)

return xmlDict

def getLink(link):

connections = []

nodes = []

nodesName = []

beautiful = urllib2.urlopen(link).read()

soup = bs4.BeautifulSoup(beautiful)

links = soup.findAll('a')

for l in links:

ln = l.get('href')

#cn = l.string

#connections.append((cn, ln))

nodes.append(ln)

return nodes

def generateNodes(graph):

""" return a list of nodes """

nodes = graph.keys()

return nodes

def generateEdges(graph):

""" return a list of tuples thath represents edges """

edges = []

for vertex in graph:

for neighbour in graph[vertex]:

if {neighbour, vertex} not in edges:

edges.append((vertex, neighbour))

return edges

def getGraph(sitemap, site='wordpress'):

""" get a dict from sitemap, to construct nodes and edges """

xml = getChild(sitemap)

documents = {}

graph0 = {}

graph = {}

siteLink = []

if site=='wordpress':

for x in xml.keys():

for k in xml[x]:

graph[k] = getLink(k)

siteLink.append(k)

print k

else:

for k in xml:

graph[k] = getLink(k)

siteLink.append(k)

print k

return graph, siteLink

def main(home, sitemap, siteType):

graph, siteLink = getGraph(sitemap, siteType)

print 'GRAPH\n\n'

#preparo i dati

## TUTTO

G = nx.Graph()

G.add_nodes_from(generateNodes(graph))

G.add_edges_from(generateEdges(graph))

#eccentricity = nx.eccentricity(G)

#pr = nx.pagerank(G)

#googleMatrix = nx.google_matrix(G)

#print 'ECCENTRICITY'

#print eccentricity

#print 'PAGE RANK'

#print pr

#print 'GOOGLE MATRIX'

#print googleMatrix

print 'EIGENVECTORS CENTRALITY'

ec = nx.eigenvector_centrality(G, max_iter=100)

fec = open('ec.csv','w')

for k in ec.keys():

fec.write(str(k)+';'+str(ec[k])+'\n')

fec.close

fdeg = open('nodeDegree.csv', 'w')

for v in G:

fdeg.write(str(v)+';'+str(float(G.degree(v)))+'\n' )

fdeg.close()

nomeFig = 'grafo.pdf'

tipoFig = 'pdf'

graph_pos=nx.spring_layout(G, iterations=400, scale=1)#, dim=10000)

print 'GRAPG POS'

for n in graph_pos:

graph_pos[n] = graph_pos[n]*100

nx.draw_networkx_nodes(G,graph_pos,node_size=[float(G.degree(v))*0.3 for v in G], alpha=0.7, node_color=[float(ec[k]) for k in G.nodes(data=False)],with_labels=False)

nx.draw_networkx_edges(G,graph_pos,width=0.1,alpha=0.5,edge_color='r', arrows=True)

nx.draw_networkx_labels(G, graph_pos,font_size=0,font_family='sans-serif')

plt.axis('off')

plt.savefig(nomeFig, format=tipoFig, dpi='9000', figsize=(32.000, 32.000)) # save as png

plt.show()

if __name__ == "__main__":

home = None

sitemap = None

siteType = None

parser = OptionParser(usage="%prog [options]")

parser.add_option("-s", "--sitemap_url", action="store", dest="sitemap_url", default=None, help="Complete url of sitemap, with http://")

parser.add_option("-p", "--homepage", action="store", dest="homepage", default=None, help="Complete url of homepage with http://")

parser.add_option("-t", "--cms_type", action="store", dest="cms_type", default="wordpress", help="CMS Type: joomla or worpress. Default: wordpress")

(options, args) = parser.parse_args()

if options.sitemap_url == None:

print 'You must specify a sitemap url'

exit()

elif str(options.sitemap_url[-4:]) != '.xml':

print "You must specify an xml sitemap"

exit()

else:

sitemap = str(options.sitemap_url)

if str(options.homepage) == None:

print 'You must specify a url'

exit()

else:

homepage = str(options.homepage)

if options.cms_type == None:

print 'You must specify a cms type: wordpress or joomla'

exit()

elif str(options.cms_type) not in ['wordpress','joomla']:

print "You must specify one choice between: wordpress, joomla"

exit()

else:

siteType = str(options.cms_type)

main(homepage, sitemap, siteType)

CHIEDI UN PREVENTIVO GRATUITO

Chiedi un preventivo per realizzare il tuo sito internet, per una consulenza SEO, lo sviluppo di un software o per realizzare una soluzione tecnologica.

Chiedi informazioni, sarai ricontattato quanto prima.

CONTATTAMI

Condividi se ti piace...

Grafo di un sito internet: un esempio in Python

MA COS’È UN GRAFO?

GRAFO DI UN SITO: PERCHÉ È IMPORTANTE

FACCIAMO UN ESEMPIO CON UN’ANALOGIA

ANDIAMO NEL DETTAGLIO

IL CODICE IN PYTHON

CODICE COMPLETO

CHIEDI UN PREVENTIVO GRATUITO

Chiedi un preventivo per realizzare il tuo sito internet, per una consulenza SEO, lo sviluppo di un software o per realizzare una soluzione tecnologica.

Articoli correlati

Redirect 301: Consigli e strumenti utili in ottica SEO

Sito web in WordPress: vantaggi in 6 punti essenziali

Ebook: Le checklist per pianificare e realizzare il tuo sito web