1 UVOD Hipergrafi so zelo splošen način predstavitve relacij med množicami objektov, še zlasti tedaj, ko relacije med objekti niso zgolj dvojiške, temveč večmestne. k-mestna relacija lahko na zgoščen način predstavlja množico dvojiških relacij med vsemi pari objektov (npr. predstavlja kliko v grafu brez naštevanja vseh k(k−1)/2 povezav med pari vozlišč). Take splošne predstavitve s hipergrafi se uporabljajo na področjih, kot so bioinfor- matika [1], klasifikacija slik [2], strojno učenje [3] in analiza (družbenih) omrežij [4]. Sosednost vozlišč v hipergrafih lahko definiramo na več načinov, to je odvisno od področja uporabe. Raz- iskave na področju analize omrežij (npr. [5], [6]) se večinoma osredotočajo na iskanje smiselnih in upo- rabnih definicij (sosednost lahko npr. predstavimo z Prejet 8. avgust, 2018 Odobren 28. september, 2018 utežjo, ki označuje število skupnih sosedov) in ne na učinkovitost izračuna definirane sosednosti. Izračun matrike sosednosti (glej razdelek 1.2) lahko prevedemo na problem množenja dveh incidenčnih ma- trik. Za ugotavljanje sosednosti zgolj enega para vozlišč je optimalna naivna metoda. Po drugi strani pa so za izračun celotne matrike sosednosti asimptotično boljša izbira metode za hitro množenje matrik. Naša predla- gana metoda se uvršča med ti skrajnosti. Pomeni nov pristop na podlagi skupin ekvivalentnih vozlišč, ki je dovolj splošen, da je lahko potencialno uporaben tudi pri reševanju kakšnega drugega algoritmičnega problema. Poglejmo si naslednji motivacijski problem. Recimo, da je bilo v preteklem letu organiziranih m konferenc. Za vsako konferenco poznamo seznam udeležencev, ki so neka podmnožica vseh n aktivnih raziskovalcev. Pred- postavimo, da se med konferenco vsi prisotni razisko- valci spoznajo med seboj. Kako lahko sedaj na učinkovit način odgovarjamo na vprašanja, ali se dva raziskovalca poznata? In če se, na kateri konferenci sta se spoznala? 1.1 Hipergrafi Hipergraf je posplošitev grafa in je sestavljen iz množice vozlišč V (n = |V |) in množice hiperpo- vezav E (m = |E|). V primerjavi s povezavami v navadnih grafih so hiperpovezave e ∈ E predstavljene s podmnožico vozlišč (e ⊆ V ) in ne vedno s točno dvema vozliščema, kot velja v navadnih grafih. Naj bo mi = |Ei| velikost i-te hiperpovezave in M = ∑ mi velikost problema oz. vhodnih podatkov. Za podrobnejšo predstavitev hipergrafov bralcu svetujemo knjigo Hyper- graph Theory [7]. Na hipergraf G(V,E) lahko gledamo na dva načina. Lahko ga obravnavamo kot družino množic ali pa kot SOSEDNOST VOZLIŠČ V HIPERGRAFIH 225 dvodelni graf. V drugem primeru prva skupina vozlišč dvodelnega grafa ustreza vozliščem V hipergrafa G, druga skupina pa povezavam E. Vozlišči dvodelnega grafa v ∈ V in e ∈ E sta povezani natanko takrat, ko je vozlišče v element množice oz. hiperpovezave e. 1.2 Sosednost vozlišč Vozlišči a, b ∈ V hipergrafa sta sosedni, če si delita katero od hiperpovezav (∃e ∈ E : a ∈ e ∧ b ∈ e). V skladu s to definicijo bi lahko hipergraf predstavili z grafom, v katerem bi vsako hiperpovezavo modelirali s kliko vozlišč. Naivni način za ugotavljanje sosednosti je, da preve- rimo vse hiperpovezave in ugotovimo, ali sta v kateri prisotni obe vozlišči, ki nas zanimata (a in b). Množico vozlišč, ki sestavljajo hiperpovezavo, lahko hranimo v razpršeni množici (angl. hash set), ki omogoča po- izvedbe o prisotnosti nekega elementa v množici v pričakovanem konstantnem času. Za ta problem obsta- jajo tudi naprednejše tehnike, ki odgovarjajo na poi- zvedbe v konstantnem času [8], [9]. Časovna zahtevnost posamezne poizvedbe o sosednosti je torej O(m). Za gradnjo matrike sosednosti, ki vsebuje podatke o sose- dnosti vseh parov vozlišč, pa s tem načinom potrebujemo O(n2m) časa. Cilj je izboljšati ta naivni pristop. 2 SORODNA DELA V matriki sosednosti lahko namesto podatka o sose- dnosti hranimo število hiperpovezav, v katerih hkrati nastopata obe vozlišči. S tem pravzaprav dobimo še podrobnejšo sliko sosednosti. Matriko števila skupnih hiperpovezav M lahko izračunamo kot produkt inci- denčne matrike A in njene transponirane matrike AT (M = AAT ). V incidenčni matriki A ustrezajo vrstice vozliščem, stolpci pa hiperpovezavam. Incidenčna ma- trika vsebuje vrednost 1 v j-tem stolpcu i-te vrstice, če je i-to vozlišče del j-te hiperpovezave, sicer je na tem mestu vrednost 0. Produkt matrik lahko izračunamo s katerim od algoritmov za hitro množenje matrik, ki ima časovno zahtevnost O(nω), ω = 2.373 [10]. Za izračun, ali obstaja skupna hiperpovezava, namesto točnega števila skupnih povezav lahko uporabimo kate- rikoli algoritem za množenje dvojiških matrik oz. matrik logičnih vrednosti. Npr. Yu je v [11] predstavil algoritem s časovno zahtevnostjo O(n3/ log4 n · (log log n)6). Iskanje skupne hiperpovezave oz. predstavnika sku- pnih hiperpovezav ustreza iskanju prič v produktu dveh matrik logičnih vrednosti. Algoritmi za iskanje takih prič so bili obravnavani v okviru problema najkrajših poti med vsemi pari vozlišč [12] in pri iskanju najnižjega skupnega prednika (angl. lowest common ancestor) vseh parov vozlišč v usmerjenih acikličnih grafih [13]. Za iskanje prič obstaja preprost algoritem z upo- rabo naključnosti (naključni algoritem tipa Las Ve- gas) s pričakovano časovno zahtevnostjo O(nω log n) [12]. Obstajajo tudi derandomizirane (deterministične) različice tega pristopa s polilogaritemsko časovno zah- tevnostjo O(nω logc n), vendar z veliko konstanto c. Galil in Margalit [14] sta predstavila drugačen de- terminističen algoritem za iskanje prič pri množenju matrik logičnih vrednosti. Njun pristop temelji na raz- bitju matrik v bloke, ki jih lahko zmnožimo z algo- ritmom za hitro množenje matrik. Tako ugotovimo, v katerem bloku se nahaja pozitivno število prič, ki jih lahko nato s podobnim postopkom rekurzivno poiščemo samo v tem bloku. Časovna zahtevnost njune rešitev je O(nω+log −1/3 n). Kowaluk s sodelavci [13] je prilagodil njun pristop za iskanje največje priče s časovno zahtev- nostjo O(n2+ 1 4−ω ) = O(n2.613), kar je pozneje Czumaj [15] izboljšal na O(n2.575). 3 PODATKOVNA STRUKTURA Podan je hipergraf G(V,E). Naša metoda temelji na postopnem izboljševanju razbitja množice [16] s kon- strukcijo in vzdrževanjem pomožnega grafa H(T, P ), ki ga imenujemo graf razredov. Vsako vozlišče t ∈ T ustreza ekvivalenčnemu razredu vozlišč t ⊆ V , kjer je ekvivalenčna relacija definirana kot sosednost vozlišč v G. Postopek vzdržuje naslednji invarianti. Vsa vozlišča v razredu t ∈ T so sosedna med seboj in za vsak par vozlišč u, v ∈ t velja, da sta u in v nekem tretjem vozlišču w ∈ V bodisi obe sosedni bodisi nobeno sosedno. Sosednost med vozliščema u in v v G, kjer u ∈ t1 in v ∈ t2, predstavimo s povezavo (t1, t2) ∈ P v grafu razredov H . S tako strukturo lahko odgovorimo na poizvedbo o sosednosti dveh vozlišč v G preprosto tako, da ugotovimo, kateremu razredu pripada vsako od vozlišč. Vozlišči sta sosednji, če pripadata istemu razredu, ali pa sta pripadajoča razreda sosednja v H . Algoritem se začne s praznim grafom razredov A={1} B={2,3,4} C’ D={8,9,10} A B D’ C={5,6,7} C D Slika 1: Sprememba grafa razredov zaradi nove hiperpovezave e (črna vozlišča), ki zajema vsa vozlišča iz razredov A in B ter del vozlišč iz razredov C in D 226 HOČEVAR, BRODNIK, MUNRO H(T = ∅, P = ∅) in množico vozlišč U , ki v vsakem trenutku vsebuje vozlišča iz V , ki niso v nobenem od razredov v T , se pravi U = V \ ⋃ T . Nato zapore- doma obravnavamo hiperpovezave e ∈ E v poljubnem vrstnem redu. Vsaka obravnavana hiperpovezava lahko doda nov razred vozlišč iz U v T in delno ali pa v celoti vsebuje katere od že vzpostavljenih razredov v T . Za vsako hiperpovezavo e ∈ E (gl. algoritem 1) obravnavamo njene delne preseke z razredi (vozlišči) Mi ∈ T , ki jih po potrebi razcepimo (ustvarimo novo vozlišče v H) tako, da ohranjamo zgoraj definirani invarianti. Odcepljeni razred razreda Mi povežemo z vsemi razredi v H , s katerimi je bil povezan razred Mi. V H ustvarimo tudi nov razred M ′, ki vsebuje vozlišča iz U ; to so tista, ki se še ne pojavijo v T . Tako pridemo do stanja, kjer je hiperpovezava e sestavljena iz množice razredov X ⊆ T , pri čemer so nekateri od njih že povezani med seboj. Na koncu sosednost med razredi v X označimo tako, da jih povežemo v kliko v H . Algoritem 1: Gradnja in poizvedba v grafu razredov function GRAFRAZREDOV.DODAJ(e) Mi ← {x | x ∈ e, RAZRED(x) = i} M ′ ← {x | x ∈ e, x ∈ U} U ← U \M ′ X ← {M ′} . novi razred bo v kliki razredov for all Mi do . razcepi razrede if |Mi|