Algoritmus šíření štítku - Label propagation algorithm - Wikipedia

Šíření štítku je částečně pod dohledem strojové učení algoritmus, který přiřazuje štítky k dříve neoznačeným datovým bodům. Na začátku algoritmu má (obecně malá) podmnožina datových bodů štítky (nebo klasifikace). Tyto štítky se v průběhu algoritmu šíří do neznačených bodů.[1]

V rámci komplexní sítě, skutečné sítě mají tendenci mít struktura komunity. Šíření štítku je algoritmus [2] pro hledání komunit. Ve srovnání s jinými algoritmy[3] šíření štítků má výhody v době chodu a množství apriorních informací potřebných o struktuře sítě (předem není nutné znát žádný parametr). Nevýhodou je, že nevyrábí žádné jedinečné řešení, ale souhrn mnoha řešení.

Fungování algoritmu

V počátečním stavu nesou uzly štítek, který označuje komunitu, do které patří. Členství v komunitě se mění na základě štítků, které mají sousední uzly. Tato změna podléhá maximálnímu počtu štítků v rámci jednoho stupně uzlů. Každý uzel je inicializován jedinečným štítkem, štítky pak difundují sítí. V důsledku toho hustě spojené skupiny rychle dosáhnou společného štítku. Když je v síti vytvořeno mnoho takových hustých (konsensuálních) skupin, pokračují v rozšiřování směrem ven, dokud to není možné.[2]

Proces má 5 kroků:[2]

1. Inicializujte štítky na všech uzlech v síti. Pro daný uzel x, CX (0) = x.

2. Nastavte t = 1.

3. Uspořádejte uzly v síti v náhodném pořadí a nastavte je na X.

4. Pro každé x ∈ X vybrané v tomto konkrétním pořadí nechte CX(t) = f (C.Xi1(t), ..., C.Xim(t), C.Xi (m + 1) (t - 1), ..., C.Xik (t - 1)). Zde vrací štítek vyskytující se s nejvyšší frekvencí mezi sousedy. Pokud existuje více štítků s nejvyšší frekvencí, vyberte štítek náhodně.

5. Pokud má každý uzel štítek, který má maximální počet jejich sousedů, pak algoritmus zastavte. Jinak nastavte t = t + 1 a přejděte na (3).

Vícenásobná struktura komunity

Na rozdíl od jiných algoritmů může šíření štítku vést k různým strukturám komunity ze stejných počátečních podmínek. Rozsah řešení lze zúžit, pokud některým uzlům budou přiděleny předběžné štítky, zatímco jiným budou ponechány bez označení. V důsledku toho se neoznačené uzly pravděpodobněji přizpůsobí označeným uzlům. Pro přesnější hledání komunit Jaccardův index se používá k agregaci několika komunitních struktur obsahujících všechny důležité informace.[2]

Reference

  1. ^ Zhu, Xiaojin. "Učení se z označených a neoznačených dat pomocí šíření štítků". CiteSeerX  10.1.1.14.3864. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ A b C d OSN Raghavan - R. Albert - S. Kumara „Algoritmus téměř lineárního času pro detekci komunitních struktur ve velkých sítích“, 2007
  3. ^ M. E. J. Newman, „Zjišťování struktury komunity v sítích“, 2004

externí odkazy