X
Utilizziamo cookie nostri e di terze parti per migliorare i servizi e analizzare le tue preferenze. Continuando la navigazione accetterai automaticamente l'utilizzo dei cookie.
Per maggiori informazioni e modificare le impostazioni visita la pagina dedicata ai cookie.

SEO

Versione Italiana | English Version | Version Française | Versión en español
Qt S60 Mobile Bluetooth Implementation
Qt Symbian HostNotFound Error

Algoritmi Genetici applicati alla tematica SEO (Search Engine Optimization)

Lo scopo del seguente articolo è quello di mostrare come un algoritmo genetico possa essere utilizzato per ottimizzare la distribuzione dei link all'interno di un sito web in modo da massimizzare il rank associato alle pagine che lo compongono.
Come prima cosa spieghiamo brevemente cosa s'intende per rank, algoritmi di link analysis ranking e algortmi genetici, per poi mostrare come l'applicazione di questi ultimi possa essere utile al posizionamento di un sito all'interno dei risultati di un motore di ricerca (SERP).

La teoria

Rank

Il rank di una pagina non è altro che un indice di gradimento (un peso numerico) della pagina stessa. Quando si effettua una interrogazione (query), su un motore di ricerca, l'elenco di siti che si ottiene è ordinato in base al rank attribuito a ciascun di essi: più alto è il rank maggiore è la possibilità che un sito appaia tra le prime posizioni dell'elenco.

Algoritmi di link analysis ranking

Un algoritmo di link analysis ranking ha lo scopo di analizzare i links contenuti all'interno delle pagine web del sito in esame, in modo da associare ad esse un determinato "rank". L'algoritmo di link analysis ranking più conosciuto è l'algoritmo PageRank, utilizzato da Google per ordinare i risultati di una ricerca.

Vediamo come un algoritmo di link analysis ranking attribuisce un determinato rank ad una pagina web.

Un sito internet non è altro che un insieme di pagine web interconnesse tra loro tramite links, componendo di conseguenza un grafo.Ciascun nodo del grafo rappresenta una pagina del sito, mentre ciascun arco uscente o entrante rappresenta un link, da e per un altro nodo. Graficamente:

grafo di esempio ( seo )

I cerchi (nodi) rappresentano le pagine di cui è composto un sito: homepage, pagina1, pagina2 ecc. Gli archi che fuoriescono da ciascun nodo rappresentano i link che da una pagina portano ad un'altra, mentre gli archi entranti in ciascun nodo rappresentano i link che puntano a quel determinato nodo.

Pagerank

Per approssimare questo algoritmo, analizziamo nel dettaglio la formula inizialmente ideata dai fondatori di Google per l'algoritmo di PageRank.

PageRank segue un percorso casuale nel grafo del web, dove ogni pagina propaga il proprio peso alle pagine verso cui ha un link, determinando un array di pesi nominati in seguito pesi di authority. L'algoritmo completo per il calcolo del PageRank fa ricorso all'uso della teoria dei processi di Markov.

Supponiamo di voler calcolare il rank della homepage dell'esempio precedente. Avremo:

Rank[A] = ( 1 - d ) + d i (Rank[Pi] / Link[Pi])
  • Rank[A] è il valore di Rank della pagina A che vogliamo calcolare
  • P[i] sono le pagine che contengono almeno un link verso A
  • Rank[Pi] sono i valori di Rank delle pagine P1 ... Pn
  • Link[Pi] sono il numero complessivo di link contenuti nella pagina che offre il link
  • d (damping factor) è un fattore deciso da Google che nella documentazione originale assume valore 0,85. Può essere aggiustato da Google per decidere la percentuale di PageRank che deve transitare da una pagina all'altra e il valore di Rank minimo attribuito ad ogni pagina in archivio.

L' algoritmo in questione è ovviamente molto più complesso ed il nostro scopo non è quello di replicarlo fedelmente, ma di ottenere un modello matematico che riesca ad approssimarlo per ottenere un "Nostro" valore di Rank che ci permetta di stabilire la bontà della struttura topologica calcolata dall'algoritmo genetico dopo che è stato applicato.

Algoritmi Genetici

Gli Algoritmi Genetici (GA) sono algoritmi adattativi usati per risolvere problemi di ricerca e ottimizzazione. Sono chiamati "Genetici" perchè simulano il processo evolutivo della specie umana teorizzato da Charles Darwin. La soluzione del problema viene codificata in una struttura dati, di solito una stringa binaria, detta gene.
Possiamo sintetizzare le caratteristiche principali degli Algoritmi Genetici in 3 punti fondamentali:

  1. Un GA lavora su una popolazione di potenziali soluzioni di un problema inizialmente generata in maniera casuale.
  2. Ad ogni iterazione la popolazione subisce una mutazione in modo che l'algoritmo possa operare ogni volta su una popolazione composta da soluzioni (individui) sempre diverse e migliori.
  3. Un GA s'interrompe quando almeno uno dei criteri d'arresto è soddisfatto

La generazione di queste popolazioni evolve verso una soluzione ottimale del problema applicando il principio della sopravvivenza del migliore. Ad ogni iterazione, infatti, l'algoritmo seleziona uno o più individui all'interno della popolazione delle soluzioni e li impiega per generare nuovi elementi della popolazione stessa, che andranno a sostituire un pari numero di individui già presenti, e a costituire in tal modo, una nuova popolazione per l'iterazione (o generazione) successiva.

L'evoluzione (il miglioramenteo della popolazione delle possibili soluzioni) avviene attraverso una parziale ricombinazione delle soluzioni. Ogni individuo trasmette parte del suo patrimonio genetico ai propri discendenti. Alla fine dell'iterazione la nuova popolazione generata viene analizzata e vengono selezionati solo gli individui (soluzioni) che meglio risolvono il problema. Tali soluzioni subiranno una nuova fase di evoluzione che genererà una nuova popolazione fino al raggiungimento di una soluzione ritenuta ottimale (fine dell'evoluzione). Ma come vengono selezionati gli individui che che meglio risolvono il problema?

La qualità di un individuo (cioé quanto è buona la soluzione per il problema) è misurata mediante una funzione detta di fitness e lo scopo di un algoritmi genetico è quello di massimizzare il risultato di tale funzione.

La funzione di fitness (che dipendente dal problema in esame) indica l'adattabilità all'ambiente da parte di un individuo:
gli individui che meglio si adattano hanno più possibilità di riprodursi e di trasmettere il proprio patrimonio genetico ai propri discendenti e quindi vengono selezionati come genitori. A partire da tali individui si genera un pari numero di individui che andranno a vanno a sostituire i genitori consentendo la formazione della generazione successiva.

I 2 metodi principali per mezzo dei quali un genitore può generare un proprio discendente sono:

Single point crossover

Questa tecnica consiste nel prendere due individui e tagliare le loro stringhe di codifica in un punto a caso. Si creano così due teste e due code. A questo punto si scambiano le teste e le code, ottenendo due nuovi geni. Il crossover non è applicato sempre, ma con una probabilità 10 . Nel caso in cui non viene applicato i figli sono semplicemente le copie dei genitori. Sperimentalmente si può vedere che il miglioramento diventa apprezzabile solo dopo un certo numero di passi.

Mutazione

La mutazione consiste nella modifica casuale di alcune parti dei geni con valore di fitness più basso, in base a coefficienti definiti inizialmente. Queste modifiche puntano a migliorare il valore della funzione per il gene in questione. In realtà non è corretto pensare di mutare solo i cromosomi con fitness più bassa; al fine di garantire una maggiore capacità esplorativa dell'algoritmo (e non finire in "buche" di ottimo locale) sono ritenute utili anche le mutazioni di cromosomi con valore di fitness alto. In definitiva le mutazioni servono soprattutto a esplorare lo spazio di ricerca, non hanno quindi scopo migliorativo.

L'applicazione

Come precedentemente spiegato, un sito web è a tutti gli effetti un grafo. Ed è al grafo del sito in esame che applicheremo l' algoritmo genetico.

La rappresentazione utilizzata è quella per matrice di adiacenza.

La matrice delle adiacenze costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi. In particolare è ampiamente utilizzata nella stesura di algoritmi che operano su grafi e in generale nella loro rappresentazione informatica.

Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto (i,j) della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice i al vertice j, altrimenti si trova uno 0.

Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun arco. Ad esempio se l'insieme dei vertici del grafo rappresenta una serie di punti su una cartina geografica, il peso degli archi può essere interpretato come la distanza dei punti che questi connettono. Nel nostro caso indicherà la quantità di link.

Nel caso della rappresentazione di grafi non orientati, la matrice è simmetrica rispetto alla diagonale principale.

Una delle caratteristiche fondamentali di questa matrice è di permettere di ottenere il numero dei cammini da un nodo i ad un nodo j che devono attraversare n nodi. Per ottenere tutto ciò è sufficiente fare la potenza n-sima della matrice e vedere il numero che compare al posto i,j.

Come precedentemente spiegato un gene è una stringa binaria, quindi una sequenza di 0 ed 1. L'idea che sta alla base di questo algoritmo è che anche una matrice può essere vista come una stringa binaria e quindi un gene. Se vogliamo infatti accedere all'elemento nella posizione X, Y di una matrice organizzata come stringa, basta applicare la seguente formula:

Value(x,y) = Matrix[ (y*matrixsize) +x ]

Applicando quindi un algoritmo genetico al grafo del sito in esame è possibile ottenere una migliore struttura topologica che migliora il rank delle singole pagine.

Sono stati studiati ed implementate altri processi di evoluzione oltre quello di crossover precedentemente spiegato, appositamente pensati per la problematica SEO.

La funzione di fitness è abbastanza complessa e tra i parametri che prende in considerazione ci sono il rank medio delle pagine obiettivo, il numero di link medio per pagina e numero di pagine nulle.

Le pagine obiettivo sono quelle pagine del sito che sono di nostro particolare interesse. Tipicamente nella maggior parte dei casi si tratta delle pagine di foglia.

Per pagina nulla si intende una pagina con valore di rank pari a 0.15 ( si deduce facilmente dalla formula di rank sopra citata), oppure dal valore stabilito dall'utente.

L'algoritmo è in grado di tenere conto anche dei vincoli editoriali e di evolversi in funzione di essi.

I risultati

Caso 1

L'applicazione ha permesso di fare nuove considerazioni su quelli che prima,forse ,erano considerate delle certezze del SEO.
Parlando con vari seo specialist, leggendo nei forum, una delle considerazioni che fa la maggior parte è che bisogna "bilanciare" la distribuzione dei link. Ovvero ( per quanto riguarda i link interni ) se una pagina da un link ad un' altra, è opportuno che quest'ultima lo ricambi, o comunque fancedo i conti della serva, per ogni pagina, tanti link uscenti ha, tanti ne deve avere entranti.
Il modello matetematico, tuttavia, sembra dire completamente l' opposto. La pagina "obiettivo", che vogliamo ottimizzare è rappresentata dal nodo 5.

Modello circolare

nodo 1 → 0.999518
nodo 2 → 0.999591
nodo 3 → 0.999652
nodo 4 → 0.999704
nodo 5 → 0.999749
Modello complesso

nodo 1 → 1.377268
nodo 2 → 1.714694
nodo 3 → 0.993759
nodo 4 → 0.544196
nodo 5 → 0.265642

Come possiamo vedere nel modello complesso, la pagina che volevamo valorizzare è stata addirittura penalizzata. Chiaramente l'esempio è abbastanza forzato, ma è comunque un semplificazione della struttura di molti siti web. L'intenzione di questo test non è ovviamente quello di suggerire un modello circolare per i Vostri siti, ma quello di mostrare come non sia scontata la validità delle strutture di cui siamo convinti.


Caso 2

A seguito i risultati dell' applicazione dell'algoritmo genetico sul sito: http://www.fratellileonelli.it
Potete vedere la rappresentazione 3D del grafo prima e dopo il processo. La dimensione delle sfere verdi indica il valore di rank delle pagine, mentre gli archi sono rappresentati in viola.

Prima l'applicazione
Prima dell' applicazione dell'algoritmo genetico
Dopo l'applicazione
Dopo l' applicazione dell'algoritmo genetico

Si nota a colpo d'occhio la sostanziale differenza tra prima e dopo il trattamento. Le sfere ( Le singole pagine web ) hanno un diametro più ampio, che significa maggiore rank, e sono molto più interconnesse.


Un estratto dei risultati dell'algoritmo genetico
Url Rank Prima Rank Dopo Variazione in %
/20.86998413.694373-34.3824
/come-raggiungerci/1.9239491.051139-45.3655
/foto/3.0787811.464144-52.444
/eventi/1.9821731.14884-42.0414
/progettazione/20.34529513.828813-32.0294
/realizzazione/20.46470313.718434-32.9654
/manutenzione/20.57415813.976818-32.0661
/potatura/20.67448814.024247-32.1664
/erbacee-perenni/29.89837522.935853-23.2873
/arbusti/26.29643116.967085-35.4776
/foto/azienda-florovivaistica-leonelli-0007/0.2154241.110144415.33
/foto/azienda-florovivaistica-leonelli-0008/0.2154240.29862138.6201
/foto/azienda-florovivaistica-leonelli-0009/0.2154240.32209349.5158
/foto/azienda-florovivaistica-leonelli-0010/0.2154240.518017140.464
/eventi/mostra-mercato/0.3184851.077961238.466
/eventi/open-day/0.3184850.40023325.6678
/erbacee-perenni/agastache/rupestris/0.2881620.38049732.0427
/erbacee-perenni/ajuga-reptans/atropurpurea/0.2881620.35359122.7053
/erbacee-perenni/alchemilla/mollis/0.2881620.43985352.6408
/erbacee-perenni/allium/karataviense/0.2886830.53878786.6362
/erbacee-perenni/allium/tuberosum/0.2886830.36386226.0422
/erbacee-perenni/allium-karataviense/ivory-queen/0.2881620.314569.16076
/erbacee-perenni/alyssum/montanum/0.2891210.45696658.0534
/erbacee-perenni/alyssum/saxatile/0.2891211.010271249.429
/foto/azienda-florovivaistica-leonelli-0001/0.2154240.29164235.3805
/foto/azienda-florovivaistica-leonelli-0002/0.2154240.26832324.5558
/foto/azienda-florovivaistica-leonelli-0003/0.2154240.28124930.5559
/foto/azienda-florovivaistica-leonelli-0004/0.2154240.33584855.9007
/foto/azienda-florovivaistica-leonelli-0005/0.2154240.35353364.1102
/foto/azienda-florovivaistica-leonelli-0006/0.2154240.31786447.5525
/erbacee-perenni/alyssum/saxatile-compactum/0.2891211.260897336.114
/erbacee-perenni/amsonia/tabernaemontana/0.2881620.54298488.4299
/erbacee-perenni/anemone/honorine-jobert/0.2900980.39012534.4802
/erbacee-perenni/anemone/konigin-charlotte/0.2900980.35142221.139
/erbacee-perenni/anemone/prinz-heinrich/0.2900981.071951269.513
/erbacee-perenni/anemone/richards-ahrends/0.2900980.43524250.0325
/erbacee-perenni/anemone/rosenschale/0.2900980.39189635.0908
/erbacee-perenni/anemone/whirlwind/0.2900980.3346415.354
/erbacee-perenni/aquilegia/vulgaris/0.2881621.104393283.254
/erbacee-perenni/aquilegia-cerualea/red-hobbit/0.2881621.041284261.353
/erbacee-perenni/aquilegia-cerulea/rose-queen/0.2881620.34679620.3473
/erbacee-perenni/aquilegia-flabellata-pumila/ministar/0.2881620.39112335.7299
/erbacee-perenni/aquilegia-hybride/biedermeier/0.2881620.4502256.2383
/erbacee-perenni/arabis-caucasica/snowball/0.2881620.39051735.5197
/erbacee-perenni/arenaria-montana/alba/0.2881620.43730651.7567
/erbacee-perenni/artemisia/powis-castle/0.2886830.34034617.896
/erbacee-perenni/artemisia/stelleriana/0.2886831.002906247.407
/erbacee-perenni/asclepias/tuberosa/0.2881620.40472340.4497
/erbacee-perenni/aster/snow-flurry/0.2881620.49603272.1363
/erbacee-perenni/aster-dumosus/kippenberger/0.2886830.34891520.8643
/erbacee-perenni/aster-dumosus/schneekissen/0.2886830.34566419.7384
/erbacee-perenni/aster-laterifolius/lady-black/0.2881620.35959524.789
/erbacee-perenni/astilboides/tabularis/0.2881620.40452240.38
/erbacee-perenni/aubretia/blue-cascade/0.2881620.34845420.9227
/erbacee-perenni/begonia/envasiana-bianca/0.2881620.40579340.8208
/erbacee-perenni/belamcanda/chinensis/0.2881620.33134714.9863
/erbacee-perenni/brunnera/macrophilla/0.2881620.44786955.4226
/erbacee-perenni/callirhoe/involucrata/0.2881620.55003990.878
/erbacee-perenni/campanula/loddon-anna/0.2891210.42371746.5537
/erbacee-perenni/campanula/porscharskyana-lisduggan/0.2891210.44134652.6511
/erbacee-perenni/campanula/poscharskyana-stella/0.2891210.35155421.5942
/erbacee-perenni/campanula-persicifolia/telham-beauty/0.2881620.47605765.2042
/erbacee-perenni/campanula-poscharskyana/eh.-frost/0.2881620.42013645.7984
/erbacee-perenni/campanula-punctata/rubriflora/0.2881620.44112653.0825
/erbacee-perenni/centaurea/pulcherrima/0.2881620.44010952.7295
/erbacee-perenni/centranthus/ruber/0.2881620.38574533.8636
/erbacee-perenni/ceratostigma/plumbaginoides/0.2881621.198788316.011
/erbacee-perenni/chrisantemum-coccineus/robin-red/0.2881620.38702934.3093
/erbacee-perenni/chrysantemum/weirichii/0.2881621.040353261.03
/erbacee-perenni/cimicifuga/racemosa/0.2881620.36412626.3612
/erbacee-perenni/convallaria-japonica/nana/0.2881620.48250567.4419
/erbacee-perenni/coreopsis/grandiflora-aureo-marginata/0.2891210.47727565.0779
/erbacee-perenni/coreopsis/verticillata-grandiflora/0.2891211.244313330.378

È importante notare come l'algoritmo abbia cercato di distribuire in maniera più omogenea il rank complessivo del sito.
Nella tabella con i risultati finali sono evidenziati in rosso i valori più significativi.

Le pagine che sono presenti nel menù come è facile immaginare sono quelle con maggiore rank, sia prima che dopo. Tuttavia il loro rank è stato abbassato in favore delle pagine obiettivo.

Ovviamente questo comportamento può essere pilotato in base alle esigenze. In questo particolare caso per il cliente era importante aumentare il rank delle pagine che contengono la descrizione della pianta, di conseguenza, l' algoritmo si è evoluto in questa direzione.

A seguito potete vedere come sono stati posizionati i link aggiuntivi calcolati dal processo:

Posizionamento del risultato dell'algoritmo genetico

Se siete interessati ad applicare ( gratuitamente ) il software descritto, è sufficiente scaricare l'applicazione genesis qui : download

L' applicazione è stata sviluppata con Qt 4.6, un framework per applicazioni multi piattaforma


Sebastiano Galazzo

tel .: +39 338 5482810

18 novembre 2008

Commenti

kgimdzZEOnzr
2011-10-25 08:22:24
Ab fab my gooldy man.

Eugenio
2009-03-17 22:06:30
argomento molto interessante! però come sempre il SEO è molto complicato da capire!!! :S

Arsenio Siani
2009-01-01 15:38:56
Davvero un post interessante!! Ottimo lavoro!

Sebastiano Galazzo
2008-12-27 15:22:42
Ciao, non serve essere esperti di algoritmi genetici per applicare il risultato del tool. Attualmente l'algoritmo ritorna un file SQL standard contenente i dati da aggiungere ad ogni singola pagina in esame. Tuttavia se gli utenti dovessero avere altre esigenze di formato, credo non sia un problema implementare altri output. Mandami via email le url dei siti da analizzare, ti daro' istruzioni dettagliate sull'installazione. Grazie, Sebastiano Galazzo

Gilberto Del Pizzo
2008-12-24 20:40:13
Ciao ho letto la tua pagina e non so nulla di algoritmi e simili ma se vuoi io mi occupo di posizionamento dei siti che facciamo e posso fare da tester relazionandoti i risultati che vengono raggiunti. Buon natale!

La tua domanda