znanost 23.4.2018 8:30

V okviru projekta Renoir do algoritma za boljše prepoznavanje virov informacij v kompleksnih omrežjih

Varšava, 23. aprila - Raziskovalci Politehnične univerze v Varšavi, ki skupaj s Slovensko tiskovno agencijo in drugimi partnerji sodelujejo v mednarodnem projektu Renoir, so razvili algoritem, ki omogoča hitrejše in bolj učinkovito iskanje virov širitve. Algoritem bi med drugim lahko uporabili za hitro lociranje virov lažnih novic ali govoric na družbenih omrežjih.

Poljska, Varšava.
Raziskovalci Politehnične univerze v Varšavi so oblikovali algoritem, ki omogoča hitrejše in bolj učinkovito iskanje virov širitve.
Foto: Robert Paluch/Scientific Reports

Študijo, v kateri je poleg poljskih znanstvenikov sodeloval tudi raziskovalec z ameriškega Politehničnega instituta Rensselaer, so objavili v znanstveni reviji Scientific Reports, ki jo izdaja Nature Publishing Group.

Kot so zapisali avtorji članka, je lociranje virov širitve pogosto pomembno, denimo iskanje prvega pacienta pri epidemiji ali pa vira govoric na družbenih omrežjih.

Živimo namreč v omreženi družbi, kjer smo vsako sekundo v interakciji s številnimi omrežji, od katerih zbiramo, procesiramo, prenašamo velike količine informacij, ki se vsako leto eksponentno povečujejo.

Vse večja medsebojna povezanost sveta pa nas izpostavlja številnim virusom, tako fizičnim kot tudi virtualnim, zavajajočim informacijam in govoricam, ki imajo lahko hude posledice.

Dober primer tega je denimo lažni tvit v zvezi z eksplozijo v Beli hiši leta 2013, ki je povzročil milijonske izgube na borzi. Drugi primer so ameriške volitve, kjer so številne lažne novice postale viralne in so lahko vplivale na izid volitev, so navedli znanstveniki.

Postalo je jasno, da je eden od največjih izzivov omrežnih in podatkovnih znanstvenikov razvoj učinkovitih metod za prepoznavanje in zaviranje širjenja nevarnih virusov, napačnih informacij ali govoric. Osnovna komponenta takšnega sistema je nedvomno hiter algoritem, ki poišče vir takšnih širitev, so zapisali raziskovalci.

Raziskovalci so izhajali iz ene od prvih odmevnejših študij na to temo, v kateri so Pinto, Thiran in Vettereli predlagali svoj algoritem PTVA. Poljski znanstveniki so ta algoritem z novim pristopom pohitrili, v določenih testiranjih pa se je izkazal celo za bolj učinkovitega. Novi algoritem, ki so ga poimenovali GMLA, namreč omogoča hitro procesiranje velikih omrežij, ki so sestavljena iz več deset tisoč vozlov, česar starejši algoritem ni bil zmožen.

Pri obeh algoritmih so ključnega pomena vozli, ki delujejo kot opazovalci v procesu širjenja ter sporočajo, kdaj jih je določena informacija dosegla. Kot je pojasnil vodja študije Robert Paluch, so lahko opazovalci ljudje ali stroji, ki javijo spremembo stanja, na primer pri ljudeh, ali so zboleli ali niso. Na družbenih omrežjih pa so opazovalci tisti, ki dovolijo vpogled v svoje dejavnosti.

Medtem ko PTVA za vsakega od opazovalcev preuči, kakšna je verjetnost, da je vir širjenja, se GMLA osredotoči le na t. i. kvalitetne opazovalce, ki so med prvimi javili širjenje. Ti so namreč najverjetneje najbližje viru, na ta način pa se postopek iskanja vira širitve bistveno pohitri. Algoritem za vsak vozel izračuna le verjetnost, da je vir širjenja, zato mora na koncu pravega še vedno izbrati človek, ko pregleda rezultate.

Raziskovalci so svoj algoritem testirali na več omrežjih v nadzorovanem okolju, kjer se je večinoma izkazal za bolj učinkovitega od PTVA. Podobno pa je bilo tudi na resničnem primeru, ko so v testiranje vključili portal za deljenje datotek Gnutella.

Kot je ocenil Paluch, je njihov algoritem predvsem boljši za omrežja z vozlišči, ki so bolj prisotna v realnem življenju, predvsem na družbenih omrežjih, ko imajo lahko ljudje tudi po tisoč in več sledilcev.

Čeprav se njihov algoritem pri vozliščih obnese bolje kot PTVA, pa je Paluch priznal, da je natančnost v teh primerih še vedno zelo slaba. Zato bo njihov naslednji korak izboljšati algoritem, da bo hitreje in bolj natančno našel verjetne vire širjenja tudi v omrežjih s številnimi vozlišči.

Algoritma se trenutno še ne da uporabiti v praksi, vendar so znanstveniki prepričani, da bi lahko z njim tudi v realnem življenju hitreje našli vire lažnih novic ali pa ga uporabili tudi za iskanje virov drugih informacij in tako zagotovili njihovo kredibilnost. Ne glede na sposobnost algoritma pa je njegova uporabnost v realnosti predvsem odvisna od tistih, ki nadzorujejo omrežja, kjer se širijo informacije in druge stvari, saj imajo le ti dostop do vozlov oz. opazovalcev.

Projekt Renoir

Znanstveniki so algoritem razvili v okviru mednarodnega projekta Renoir, katerega cilj je analizirati širjenje informacij v spletnem medijskem prostoru ter na spletnih družbenih omrežjih.

Namen projekta Renoir je kompleksnost dinamike širjenja informacij v družbi preučiti ob sodelovanju strokovnjakov za družbene vede, novinarjev in znanstvenikov, ki se ukvarjajo z analizami velikih količin podatkov ter kompleksnimi sistemi.

Poglavitni cilj je ugotoviti, kako se informacije širijo v medijih in na spletu, ter nato poskušati z analiziranjem velikih količin podatkov izdelati model, ki lahko širjenje razloži in v končni fazi morda tudi predvidi.

Projekt koordinira Politehnična univerza v Varšavi, poleg STA pa v projektu kot partnerja nastopata še slovenski Institut Jožef Stefan in Politehnična univerza v Vroclavu.

Kot zunanji partnerji v projektu sodelujejo še ameriški Politehnični institut Rensselaer, singapurska Tehniška univerza Nanyang ter ameriške univerze Stanford, UC Santa Cruz, UC Davis, Carnegie Mellon, Northeastern in Notre Dame.

Projekt Renoir sofinancira Evropska unija v okviru evropskega programa za raziskave in inovacije Obzorje 2020, in sicer v okviru podprograma Marie Sklodowska Curie. Ta je osredotočen na razvoj človeških virov v znanosti, razvoj raziskovalnega in inovativnega dela ter povečanje strokovnih kompetenc raziskovalcev.