Elektrotehniški vestnik 85(5): 224-228, 2018 Izvirni znanstveni članek
Sosednost vozlišč v hipergrafih
Tomaž Hočevar1, Andrej Brodnik1'2, J. Ian Munro3
1	Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Večna pot 113, 1000 Ljubljana, Slovenija
2	Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijsko tehnologijo, Glagoljačka 8, 6000 Koper, Slovenija
3David R. Cheriton School of Computer Science, Univerza v Waterlooju, Waterloo ON, Kanada N2L 3G1 E-počta: tomaz.hocevar@fri.uni-lj.si
Povzetek. V članku predstavimo algoritem za odgovarjanje na poizvedbe o sosednosti vozlišč v hipergrafu ali za zgraditev celotne matrike sosednosti. V primerjavi z naivno metodo preverjanja vseh hiperpovezav je algoritem hitrejši za logaritemski faktor. V hipergrafu z n vozlišči, m hiperpovezavami in vsoto velikosti hiperpovezav M odgovarja predstavljeni algoritem na posamezne poizvedbe o sosednosti v času O(-ogm), s časovno zahtevnostjo predprocesiranja O (M + ). Temelji na novem pristopu ekvivalenčnih razredov vozlišč. Predstavljen pristop je prenosljiv tudi na problem iskanja prič pri izračunu produkta dveh matrik z logičnimi oz. dvojiškimi vrednostmi.
Ključne besede: sosednost, hipergraf, mnozenje matrik, priča, ekvivalentnost
Node adjacency in hypergraphs
We present an algorithm for answering adjačenčy queries or building an adjačenčy matrix in a hypergraph. The algorithm exhibits a logarithmič speed-up čompared to a naive method of examining all hyperedges. In a hypergraph with n nodes, m hyperedges and sum of hyperedge sizes M, it answers individual adjačenčy queries in O( -ogm), with
a O(M + ) prepročessing time. It represents a new approačh based on equivalenče člasses of nodes. The results are also appličable to detečting witnesses in Boolean matrix produčts.
Keywords: adjačenčy, hypergraph, matrix produčt, witnesses, equivalenčy
1 Uvod
Hipergrafi so zelo splošen način predstavitve relačij med mnozičami objektov, še zlasti tedaj, ko relačije med objekti niso zgolj dvojiške, temveč večmestne. k-mestna relačija lahko na zgoščen način predstavlja mnozičo dvojiških relačij med vsemi pari objektov (npr. predstavlja kliko v grafu brez naštevanjavseh k (k — 1) / 2 povezav med pari vozlisščš). Take splosšne predstavitve s hipergrafi se uporabljajo na področjih, kot so bioinfor-matika [1], klasifikačija slik [2], strojno učenje [3] in analiza (druzbenih) omrezij [4].
Sosednost vozlišč v hipergrafih lahko definiramo na več načinov, to je odvisno od področja uporabe. Raziskave na področju analize omrezij (npr. [5], [6]) se večinoma osredotočajo na iskanje smiselnih in uporabnih definičij (sosednost lahko npr. predstavimo z
Prejet 8. avgust, 2018 Odobren 28. september, 2018
utezjo, 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 mnozenja dveh inčidenčnih matrik. Za ugotavljanje sosednosti zgolj enega para vozlišč je optimalna naivna metoda. Po drugi strani pa so za izračun čelotne matrike sosednosti asimptotično boljša izbira metode za hitro mnozenje matrik. Naša predlagana metoda se uvršča med ti skrajnosti. Pomeni nov pristop na podlagi skupin ekvivalentnih vozlisščš, ki je dovolj splosšen, da je lahko potenčialno uporaben tudi pri resševanju kaksšnega drugega algoritmičšnega problema.
Poglejmo si naslednji motivačijski problem. Rečimo, da je bilo v preteklem letu organiziranih m konferenč. Za vsako konferenčo poznamo seznam udelezenčev, ki so neka podmnoziča vseh n aktivnih raziskovalčev. Predpostavimo, da se med konferenčo vsi prisotni razisko-valči spoznajo med seboj. Kako lahko sedaj na učinkovit način odgovarjamo na vprašanja, ali se dva raziskovalča poznata? In če se, na kateri konferenči sta se spoznala?
1.1 Hipergrafi
Hipergraf je posplošitev grafa in je sestavljen iz mnoziče vozlišč V (n = \V|) in mnoziče hiperpovezav E (m = \E\). V primerjavi s povezavami v navadnih grafih so hiperpovezave e G E predstavljene s podmnozičo vozlišč (e C 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 = J2 mi velikost problema oz. vhodnih podatkov. Za podrobnejšo predstavitev hipergrafov bralču svetujemo knjigo Hypergraph Theory [7].
Na hipergraf G (V, E) lahko gledamo na dva načina. Lahko ga obravnavamo kot druzšino mnozšič 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 G V in e G E sta povezani natanko takrat, ko je vozlišče v element mnozice oz. hiperpovezave e.
1.2 Sosednost vozlišč
Vozlišči a, b G V hipergrafa sta sosedni, če si delita katero od hiperpovezav (3e G E: a G e A b G e). V skladu s to definičijo bi lahko hipergraf predstavili z grafom, v katerem bi vsako hiperpovezavo modelirali s kliko vozlišč.
Naivni način za ugotavljanje sosednosti je, da preverimo vse hiperpovezave in ugotovimo, ali sta v kateri prisotni obe vozlišči, ki nas zanimata (a in b). Mnozičo vozlišč, ki sestavljajo hiperpovezavo, lahko hranimo v razpršeni mnoziči (angl. hash set), ki omogoča poizvedbe o prisotnosti nekega elementa v mnozšiči v pričšakovanem konstantnem čšasu. Za ta problem obstajajo tudi naprednejše tehnike, ki odgovarjajo na poizvedbe 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 vozlisščš, pa s tem načšinom potrebujemo O(n2m) časa. Čilj je izboljšati ta naivni pristop.
2 Sorodna dela
V matriki sosednosti lahko namesto podatka o sose-dnosti hranimo sštevilo hiperpovezav, v katerih hkrati nastopata obe vozlišči. S tem pravzaprav dobimo še podrobnejsšo sliko sosednosti. Matriko sštevila skupnih hiperpovezav M lahko izračšunamo kot produkt inči-denčne matrike A in njene transponirane matrike AT (M = AAT). V inčidenčni matriki A ustrezajo vrstiče vozlisščšem, stolpči pa hiperpovezavam. Inčidenčšna matrika vsebuje vrednost 1 v j-tem stolpču i-te vrstiče, če je i-to vozlišče del j-te hiperpovezave, sičer je na tem mestu vrednost 0. Produkt matrik lahko izračunamo s katerim od algoritmov za hitro mnozenje matrik, ki ima časovno zahtevnost O(nw),w = 2.373 [10].
Za izračun, ali obstaja skupna hiperpovezava, namesto točšnega sštevila skupnih povezav lahko uporabimo katerikoli algoritem za mnozenje 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 skupnih hiperpovezav ustreza iskanju prič v produktu dveh matrik logičnih vrednosti. Algoritmi za iskanje takih prič so bili obravnavani v okviru problema najkrajsših poti med vsemi pari vozlišč [12] in pri iskanju najnizjega skupnega prednika (angl. lowest common ancestor) vseh parov vozlišč v usmerjenih ačikličnih grafih [13].
Za iskanje prič obstaja preprost algoritem z uporabo naključnosti (naključni algoritem tipa Las Vegas) s pričakovano časovno zahtevnostjo O(nw log n) [12]. Obstajajo tudi derandomizirane (deterministične)
različice tega pristopa s polilogaritemsko časovno zahtevnostjo O(nw logc n), vendar z veliko konstanto c.
Galil in Margalit [14] sta predstavila drugačen determinističen algoritem za iskanje prič pri mnoZenju matrik logičnih vrednosti. Njun pristop temelji na razbitju matrik v bloke, ki jih lahko zmnozimo z algoritmom za hitro mnozenje 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(nw+log n). Kowaluk s sodelavči [13] je prilagodil njun pristop za iskanje največje priče s časovno zahtevnostjo O(n2+) = 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 mnoziče [16] s kon-strukčijo in vzdrzevanjem pomoznega grafa H (T, P), ki ga imenujemo graf razredov. Vsako vozlišče t G T ustreza ekvivalenčnemu razredu vozlišč t C V, kjer je ekvivalenčna relačija definirana kot sosednost vozlišč v G. Postopek vzdrzuje naslednji invarianti. Vsa vozlišča v razredu t g T so sosedna med seboj in za vsak par vozlišč u, v G t velja, da sta u in v nekem tretjem vozlišču w g V bodisi obe sosedni bodisi nobeno sosedno. Sosednost med vozliščema u in v v G, kjer u G t1 in v G t2, predstavimo s povezavo (t1,t2) G P v grafu razredov H. S tako strukturo lahko odgovorimo na poizvedbo o sosednosti dveh vozlisščš 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
.•'' B={2,3,4}	D={8,9,10}
/ ©
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 = 0, P = 0) 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 \ U T. Nato zaporedoma obravnavamo hiperpovezave e G 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 ze vzpostavljenih razredov v T.
Za vsako hiperpovezavo e G E (gl. algoritem 1) obravnavamo njene delne preseke z razredi (vozlišči) Mi G T, ki jih po potrebi razcepimo (ustvarimo novo vozlišče v H) tako, da ohranjamo zgoraj definirani invarianti. Odcepljeni razred razreda Mi povezš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 mnoziče razredov X C T, pri čemer so nekateri od njih ze povezani med seboj. Na konču sosednost med razredi v X označimo tako, da jih povezemo v kliko v H.
Algoritem 1: Gradnja in poizvedba v grafu razredov
function GRAFRAZREDOV.DODAJ(e)
Mi ^ {x | x G e, RAZRED(x) = i} M' ^ {x | x G e, x G U} U ^ U \ M'
X ^ {M'} > novi razred bo v kliki razredov for all Mi do	> razčepi razrede
if |Mi| < VELIKOSTRAZREDA(i) then
X ^ X U { RAZČEPl(i) } else
X ^ X U {Mi} for all x G X do	> naredi kliko razredov
for all y G X do
if not SOSEDNJA(x, y) then POVEZl(x, y)
function GrafRazredov.Poizvedba(o, b) A ^ RAZRED(a) B ^ RAZRED(b)
return A = B V Sosednja(A, B)
Postopek, opisan v algoritmu 1, ilustrira slika 1 na primeru dodajanja hiperpovezave e = {1, 2, 3,4,5, 8, 9}. Vozlišča hiperpovezave najprej razdelimo v mnoziče Mi glede na pripadnost vozlišč hiperpovezave e obstoječim razredom. Tako v podanem primeru dobimo MA = {1},Mb = {2,3,4},MC = {5} in MD = {8,9}. Razred M', ki vsebuje nova vozlišča, je prazen. Sedaj za vsako mnozšičo Mi, ki ne zajema čelotnega razreda (v primeru sta to MC in MD), odčepimo del vozlišč iz razreda. Odčepljena dela razredov C' in D' podedujeta tudi povezave, ki so sosednje razredoma C in D, kar je označeno z rdečimi črtami. Elemente mnoziče razredov X = {A, B, C', D'}, ki jih sedaj v čeloti zajema hiperpovezava e, povezemo v H med seboj z modrimi pove-
zavami v kliko. Pri tem naj opozorimo, da so nekatere povezave iz P obravnavane večkrat (na sliki so označene s črtkano črto). Povezava (A, B) je obstajala ze pred dodatkom nove hiperpovezave, povezava (C', D') pa je bila dodana pri odčepitvi dveh povezanih razredov.
Sosednost dveh vozlisščš u, v G V določšimo tako, da ugotovimo, kateremu razredu v H pripada vsako od njiju. Če gre za isti razred, ali pa sta ta dva razreda povezana v H, sta vozlišči u in v sosednji.
Očenimo časovno zahtevnost gradnje H (T, P). Z nH(l) označimo število razredov |T;| po l obravnavanih hiperpovezavah. Velja nH (0) = 0, za l > 1 pa nH(l) < 2nH(l - 1) + 1 in zato nH(l) < 2;. Podobno definirajmo mH(l) < 22; kot število povezav med razredi, |P;|. Naj bo f(l) število operačij, kijih zahteva dodatek l-te hiperpovezave. Za vsako od m; vozlišč l-te hiperpovezave moramo ugotoviti, kateri skupini pripada. Poleg tega je morda treba pri odčepitvi dela skupine podvojiti vse obstoječe povezave (22(l-1)) in na konču obravnavati (povezati) vse pare skupin, ki so del hiper-povezave (nH(l)2). Za število operačij torej velja f (l) < m; + 22(l-1) + 22; in	f (l) = O(M + 22m), kjer
je M vsota velikosti hiperpovezav (M = m;).
(Časovna zahtevnost predlaganega algoritma je eksponentna v odvisnosti od sštevila hiperpovezav, kar je učšinkovito in smiselno samo za majhne vrednosti m v primerjavi z naivno metodo s časovno zahtevnostjo O(n2m). Učinkovitost opisanega pristopa pri manjšem sštevilu hiperpovezav pa lahko kljub temu izkoristimo tako, da hiperpovezave razdelimo v m skupin velikosti k in za vsako skupino posebej zgradimo graf razredov, kar zahteva O(M + m22fc) časa. Za odgovor na poizvedbo o sosednosti dveh vozlišč moramo preveriti vseh m skupin, v posamezni skupini pa lahko s pomočšjo grafa razredov izračšunamo odgovor na poizvedbo v konstantnem čšasu. Algoritem 2 povzema opis pročesa gradnje struktur in odgovarjanja na poizvedbe.
Algoritem 2: Izračun sosednosti vozlišč v hipergrafih
function Predobdelava(V, E, k) n, m ^ |V|, |E|
for i = 1 to m do
> razdeli v skupine
Si = ^^(i-!^ . . . , Eifc}
for i = 1 to m do
> zgradi grafe razredov
Hi ^ GrafRazredov() for all e G Si do
Hi .DODAJ(e)
function POIZVEDBA(a, b)
for i = 1 to mm do > poizveduj v vseh skupinah if Hi .PoiZVEDBA(a, b) then return Da return Ne
Izbira velikosti skupine, k, je kompromis med hitrostjo gradnje grafov razredov in hitrostjo poizvedb. Večji
SOSEDNOST VOZLIŠČ V HIPERGRAFIH
227
ko je k, hitrejše so poizvedbe, ker je treba obravnavati manj skupin hiperpovezav. Po drugi strani pa večji k močno vpliva na učinkovitost gradnje grafov razredov. Daje čas gradnje polinomski (in ne eksponenten), mora biti k logaritmičen. Primer take izbire je k = e i log m, ki vodi do naslednjega izreka.
Izrek 1: Na poizvedbe o skupni povezavi para vozlisc v hipergrafu z n vozlišči in m hiperpovezavami z vsoto velikosti M lahko z O(M + -f) predprocesiranja odgovarjamo v casu O(-Ogf)•
Če zelimo zgraditi celotno matriko sosednosti, torej odgovoriti na vseh n2 mogočih poizvedb, morata biti čas predprocesiranja in čas, namenjen poizvedbam, uravnotezena. Optimalna izbira za k je v tem primeru
k = log n.
Iskanje skupnih hiperpovezav je povezano s problemom iskanja prič produkta AAT, kjer je A matrika logičšnih vrednosti. Predstavljeni algoritem lahko uporabimo za izračun poljubnega produkta AB dveh matrik logičšnih vrednosti, in sičer tako, da iz njiju sestavimo pomozno matriko C (glej enačbo 1). Produkt matrike C s transponirano vrednostjo pa v rezultatu vsebuje iskano vrednost AB kot podmatriko. Izbira k = log n v izreku 1) nas vodi do naslednje poslediče:
C -
A BT
CC T
CT = [AT B] ,
'AAT AB" BtAt BtB
(1)
ki jih kopiramo, do spremembe. Ker pa nikoli ne pride večš do pisanja (spreminjanja) v seznamu, ki ga zšelimo kopirati, lahko vzdrzujemo seznam v času O(1) na kopiranje.
o={h,i,j}
□ -» j -> i h
(aojo
i *-^ _.»** i
pc_riV
o2={h,i,j,k}
i *■ ,'' i
v :	: |
G) o ={h,i,j,k} CD
□ -» j -» i -» h
o
□ -»K
o
o
-» k
Posledica 1: Price produkta matrik logičnih vrednosti A in B dimenzije n x n lahko izračunamo v casu
log n )*
4 Razširitve
Opisana podatkovna struktura se osredotoča zgolj na obstoj skupne hiperpovezave, lahko pa bi jo preprosto prilagodili tudi za iskanje primera hiperpovezave ali price, ki je lahko poljubna ali pa največja. Za to bi morali v grafu razredov H hraniti oznake na vozliščih in povezavah, ki bi nam povedale, katera hiperpovezava je bila vzrok za vzpostavitev razreda ali povezave med razredoma. Če vozlišči a in b pripadata razredoma A in B, odgovorimo na poizvedbo o njuni skupni hiperpove-zavi, če je A = B, kar z oznako njunega razreda, sicer pa z oznako povezave med A in B v grafu razredov.
Podatkovna struktura je dovolj splošna, da dovoljuje tudi poročanje seznama vseh hiperpovezav, ki so skupne dvema vozliščema v G. Sprememba je podobna kot v prejšnjem primeru, le da namesto posamezne oznake na vozliščih in povezavah v grafu razredov, hranimo sezname oznak. Sedaj je v primeru odčepitve (dela) razreda treba podvojiti (kopirati) čeloten seznam oznak. Pri tem uporabimo tehniko COW (angl. copy on write), ki dejansko kopiranje izvede šele, če je prišlo v podatkih,
Slika 2: Primer podvajanja seznama oznak brez kopiranja
Slika 2 prikazuje opisani postopek na primeru kopiranja oznake Oi na povezavi med razredoma A in B. Zgornja slika prikazuje začetno stanje, kjer so v seznamu Oi shranjene hiperpovezave H, I in J. Ce dodamo hiperpovezavo K, ki vključuje črno pobarvana vozlišča, moramo odčepiti razreda A' in B', kar je prikazano na srednji sliki. Tako med novimi povezavami, ki so nakazane s čšrtkanimi čšrtami, nastane tudi povezava med razredoma A' in B' z oznako O2 = Oi U {K}. Sedaj lahko brez škode dodamo tudi nove hiperpovezave v Oi, kar je ilustrirano na spodnji sliki. Nova hiperpovezava L (označena s črnimi vozlišči), ki zajema čelotna razreda A in B, doda oznako L v seznam Oi. Vanj jo lahko vključimo brez vpliva na O2, ki se sičer skličuje na Oi.
Ker smo mnozičo hiperpovezav E razdelili na ^f skupin velikosti k = log m, na poizvedbo odgovorimo tako, da zdruzimo ff disjunktnih seznamov, ki jih dobimo s poizvedbami v vsakem od grafov razredov. To zahteva O(+ occ) časa, pri čemer je occ dolzina iskanega seznama skupnih hiperpovezav.
5 Sklep
S preprostim algoritmom smo demonstrirali, kako lahko pri ugotavljanju sosednosti vozlisščš v hipergrafu pridemo do pohitritve za logaritemski faktor. Pristop, ki temelji na skupinah ekvivalentnih vozlišč, je dovolj splošen, da dovoljuje tudi številne prilagoditve. Lahko z njim morda dosezemo še večje pohitritve? Čeprav število skupin v pomozšnem grafu narasščša eksponentno, pa nikoli ne preseze n, ker nobena skupina ne more biti prazna.
a
b
o
o
228
HOČEVAR, BRODNIK, MUNRO
Taka visoka segmentacija se običajno pojavi skupaj s številnimi povezavami med skupinami. Morda bi lahko z dobro strategijo zdruZevanja razredov grafu razredov hevristično ohranjali manjše število skupin in povezav. Razreda sta ekvivalentna in ju lahko združimo, če sta povezana in imata enako mnozico sosedov. Zaznavanje ekvivalentnih skupin bi lahko izvajali učinkovito npr. z uporabo prstnih odtisov mnozice sosedov. Kljub temu pa ni očitno, kakšen bi bil vpliv vmesnega zdruzevanja na cšasovno zahtevnost algoritma.
[16] M. Habib, C. Paul, and L. Viennot, "Partition Refinement Techniques: An Interesting Algorithmic Tool Kit", International Journal of Foundations of Computer Science, vol. 10, no. 02, pp. 147-170, jun 1999.
Tomaž Hočevar je diplomiral in leta 2018 doktoriral s področja računalništva in informatike na Univerzi v Ljubljani. Na Fakulteti za računalništvo in informatiko je zaposlen kot asistent. Njegovo raziskovalno področje lezi na preseku analize omrezij in algoritmov ter podatkovnih struktur.
Zahvala
Raziskavo je omogočila Javna agencija za raziskovalno dejavnost Republike Slovenije (ARRS) v okviru programov P2-0209 in P2-0359 ter projekta N2-0053.
Poleg tega sta raziskavo omogočila se Canada Research Chairs Programme in Natural Science and Engineering Council of Canada.
Andrej Brodnik je redni profesor računalništva in informatike na Univerzi na Primorskem in predava tudi na Univerzi v Ljubljani. Njegovo osnovno raziskovalno področšje so podatkovne strukture in algoritmi. Posebno pozornost namenja vplivom spoznanj teoretičšnih raziskav na praktične rešitve. Objavlja še s področja kombinatorične optimizačije, še posebej v povezavi z bioinformatiko. Veliko pozornosti namenja razvoju poučševanja račšunalnisštva v osnovnih in srednjih šsolah.
Literatura
[1]	S. Klamt, U.-U. Haus, and F. Theis, "Hypergraphs and Cellular Networks", PLoS Computational Biology, vol. 5, no. 5, p. e1000385, may 2009.
[2]	Jun Yu, Dacheng Tao, and Meng Wang, "Adaptive Hypergraph Learning and its Application in Image Classification", IEEE Transactions on Image Processing, vol. 21, no. 7, pp. 32623272, jul 2012.
[3]	D. Zhou, J. Huang, and B. Scholkopf, "Learning with Hypergraphs: Clustering, Classification, and Embedding", Advances in Neural Information Processing Systems 19, vol. 19, pp. 16011608, 2007.
[4]	E. Estrada and J. A. Rodriguez-Velazquez, "Subgraph centrality and clustering in complex hyper-networks", Physica A: Statistical Mechanics and its Applications, vol. 364, pp. 581-594, 2006.
[5]	K.-I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal, and A.-L. Barabasi, "The human disease network", Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no. 21, pp. 8685-8690, 2007.
[6]	K. A. Zweig and M. Kaufmann, A systematic approach to the one-mode projection of bipartite graphs, 2011, vol. 1, no. 3.
[7]	A. Bretto, Hypergraph Theory, ser. Mathematical Engineering. Heidelberg: Springer International Publishing, 2013.
[8]	A. Brodnik and J. I. Munro, "Membership in constant time and minimum space", in Lecture Notes in Computer Science. Springer-Verlag, 1994, pp. 72-81.
[9]	A. Brodnik and J. I. Munro, "Membership in constant time and almost-minimum space", SIAM Journal on Computing, 1999.
[10]	F. Le Gall, "Powers of tensors and fast matrix multiplication", in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14. New York, New York, USA: ACM Press, 2014, pp. 296-303.
[11]	H. Yu, "An Improved Combinatorial Algorithm for Boolean Matrix Multiplication", in International Colloquium on Automata, Languages, and Programming, 2015, pp. 1094-1105.
[12]	R. Seidel, "On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs", Journal of Computer and System Sciences, vol. 51, no. 3, pp. 400-403, dec 1995.
[13]	M. Kowaluk and A. Lingas, "LCA Queries in Directed Acyclic Graphs", in Proceedings of the 32nd international conference on Automata, Languages and Programming, 2005, pp. 241-248.
[14]	Z. Galil and O. Margalit, "Witnesses for Boolean Matrix Multiplication and for Transitive Closure", Journal of Complexity, vol. 9, no. 2, pp. 201-221, jun 1993.
[15]	A. Czumaj, M. Kowaluk, and A. Lingas, "Faster algorithms for finding lowest common ancestors in directed acyclic graphs", Theoretical Computer Science, vol. 380, no. 1-2, pp. 37-46, jun 2007.
J. Ian Munro je redni profesor in Canada Research Chair za načrtovanje algoritmov na Univerzi v Waterlooju, kjer deluje ze od leta 1971. Poleg tega je član osrednjega svetovnega zdruzenja za računalništvo in informatiko Association for Computing Machinery in Royal Society of Canada ter prejemnik nagrade za zivljenjsko delo CS-Can.