Zdeněk Hejl bloguje

O internetu a internetovém marketingu

Link building s využitím teorie grafů

Vlastníte-li portfolio více samostatných webů, určitě se zajímáte o to, jak efektivně odkazovat z jednoho webu na jiný, aby výsledek tohoto snažení byl maximální. Pro vyřešení této link building úlohy lze využít poznatky teorie grafů, konkrétně pak algoritmus pro nalezení maximální kostry grafu.

Co jsou to grafy?

Co si představit pod pojmem graf? Většině se asi vybaví grafy např. z Excelu. V teorii grafů je však za graf považována množina vrcholů a hran, které je spojují. Jednotlivé hrany mohou mít stanovenou orientaci (je určen směr, kterým hrana vede např. od vrcholu A do vrcholu B) a nastavené ohodnocení hrany. Podle těchto dvou hledisek lze potom grafy dělit na:
  • orientované a neorientované,
  • ohodnocené a neohodnocené.
V tomto příspěvku budou využívány grafy neorientované a ohodnocené. Příklad takového grafu lze nalézt na obrázku.

 Využití grafů při návrhu odkazových schémat

Při plánování a návrhu odkazových schémat, tj. ze kterého našeho webu povede odkaz na jiný náš web, lze velice snadno využít teorie grafů a algoritmu pro hledání maximální kostry.
Postup nalezení optimálního odkazového schématu:
  1. vytvoření neohodnoceného a neorientovaného grafu, jehož vrcholy budou představovány jednotlivými weby a bude obsahovat všechny možné hrany,
  2. přiřazení ohodnocení jednotlivým hranám,
  3. provedení algoritmu pro nalezení maximální kostry grafu.

Možnosti ohodnocení hran

Nejdůležitější částí celého postupu je určení, jakým způsobem ohodnotit jednotlivé hrany. Vzhledem k tomu, že důležitým faktorem při výběru zdroje a cíle odkazu je jejich ohodnocení ze strany vyhledávačů, je vhodné využít tyto charakteristiky tj. především Google PageRank či Seznam S-Rank.

Při využití pouze jedné charakteristiky je možné pro ohodnocení hrany využít aritmetický průměr nebo součet ohodnocení webů, které hrana spojuje. Obě ohodnocení mají stejnou vypovídací hodnotu a záleží pouze na osobní preferenci, které z nich se použije.

Při použití více charakteristik jednotlivých webů je již nutné začít pracovat s váhami a normalizací jednotlivých charakteristik tj. je potřeba stanovit relativní důležitost charakteristiky vzhledem k ostatním použitým charakteristikám a převést hodnoty na škálu porovnatelných hodnot.

Při práci s váhami je vhodné dodržovat pravidlo, že součet jednotlivých vah by měl být roven 1. Při normalizaci se snažíme všechny charakteristiky transformovat na škálu od 0 do 1. Celý proces ohodnocení hrany lze shrnout následovně:
  1. určení minimální a maximální hodnoty každé charakteristiky ze všech webů v grafu,
  2. normalizace každé charateristiky pro každý web v grafu podle vzorce (hod - min) / (max - min), kde hod představuje původní hodnotu charakteristiky a min resp. max představují zjištěnou minimální resp. maximální hodnotu dané charakteristiky,
  3. přiřazení vah jednotlivým charakteristikám,
  4. výpočet souhrnné charakteristiky webu jako součtu vážených normalizovaných hodnot jednotlivých charakteristik,
  5. ohodnocení hrany jako aritmetického průměru nebo součtu souhrnných charakteristik webů, které hrana spojuje.

Maximální kostra grafu

Maximální kostru grafu lze definovat jako podmnožinu původního grafu, která obsahuje všechny vrcholy původního grafu, ale pouze některé hrany, které jsou vybrány tak, aby v grafu nevznikl cyklus a aby součet ohodnocení jednotlivých vybraných hran byl maximální.
Algoritmus výběru hran:
  1. vytvoření seznamu hran a jejich ohodnocení,
  2. seřazení seznamu podle ohodnocení sestupně,
  3. výběr hrany (hran) s nejvyšším ohodnocením a její (jejich) přesunutí do seznamu vybraných hran,
  4. vznikne-li přidáním hrany do seznamu vybraných hran cyklus, hrana se ze seznamu vymaže,
  5. pokud seznam vybraných hran obsahuje n-1 prvků, kde n je počet vrcholů grafu, pak seznam vybraných hran reprezentuje maximální kostru grafu; jinak zpět na krok 3.