Technical gazette, Vol. 22 No. 2, 2015.
Original scientific paper
https://doi.org/10.17559/TV-20150317103835
Učinkoviti višekriterijski algoritam za detekciju zajednice u složenim mrežama
Kun Deng
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Jian-Pei Zhang
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Jing Yang
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Abstract
Detekcija zajednice u složenim mrežama često se smatra problemom jednokriterijske optimizacije, a teško je jednokriterijskom optimizacijom identificirati moguću strukturu zajednice punu značenja. Stoga je algoritam višekriterijske optimizacije primijenjen na područje detekcije zajednice. Međutim, algoritam višekriterijske detekcije zajednice sklon je lokalnoj optimizaciji i slaboj raznovrsnosti niza Pareto-optimalnih rješenja. Imajući to u vidu, u ovom se radu predlaže višekriterijski algoritam za detekciju zajednice, nazvan I-NSGAII, zasnovan na sustavu NSGAII. Taj algoritam može simultano optimizirati dvije suprotstavljene kriterijske funkcije procjenjujući gustoću veza unutar zajednice i nedostatak veza između zajednica te dobiti niz Pareto optimalnih rješenja koja imaju strukturu zajednice različitih hijerarhija; on također predlaže razvojnu strategiju raznolikosti (diverziteta), omogućujući algoritmu proširenje područja pretraživanja te tako izbjegava lokalnu optimizaciju niza Pareto-optimalnih rješenja. Uz to, kako bi se poboljšala mogućnost pretraživanja algoritma, I-NSGAII algoritam usvaja strategije predstavljanja susjedstva prema mjestu (locus-based adjacency
representation), jedinstvenog naziva, crossovera u jednom smjeru i lokalne mutacije. Ispitivanja na sintetičkim i mrežama stvarnog svijeta te usporedbe s mnogim state-of-the-art algoritmima potvrđuju validnost i izvedivost I-NSGAII-a.
Keywords
NSGAII; razvojna strategija diverziteta; složene mreže; višekriterijska detekcija zajednice
Hrčak ID:
138083
URI
Publication date:
22.4.2015.
Visits: 2.093 *