/-% UPORABNA 03 INFORMATIKA think South East Europe Where technology meets Humanity m VSEBINA UPORABNA INFORMATIKA 2018 ŠTEVILKA 3 JUL/AVG/SEP LETNIK XXVI ISSN 1318-1882 B Pogled v zgodovino Janez Grad Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU 89 Znanstveni prispevki Ciril Bohak, Jože Guna, Peter Škrlj, Alja Isakovic, Matija Marolt A usability comparison of input devices for precise and intuitive interaction with 3D visualizations 94 Vitjan Zavrtanik, Lovro Šubelj Community detection in Slovene public spending 107 Jaka Šircelj, Romi Koželj, Lovro Šubelj Effects of species extinction on ecosystems stability 118 Informacije Iz Islovarja 128 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 87 UPORABNA INFORMATIKA 2018 številka 2 apr/maj/jun letnik xxvi issn 1318-1882 Ustanovitelj in izdajatelj Slovensko društvo INFORMATIKA Litostrojska cesta 54, 1000 Ljubljana Predstavnik Niko Schlamberger Odgovorni urednik Saša Divjak Uredniški odbor Marko Bajec, Vesna Bosilj Vukšic, Sjaak Brinkkemper, Gregor Hauc, Jurij Jaklič, Andrej Kovacic, Jan von Knop, Jan Mendling, Miodrag Popovic, Katarina Puc, Vladislav Rajkovič, Ivan Rozman, Pedro Simöes Coelho, John Taylor, Mirko Vintar, Tatjana Welzer Družovec, Slavko Žitnik Recenzenti Alenka Baggia, Marko Bajec, Marko Bohanec, Renato Burazer, Janez Demšar, Dejan Dinevski, Saša Divjak, Nadja Dobnik, Jure Erjavec, Aleksandar Gavrič, Miro Gradisar, Aleš Groznik, Tanja Grubljesič, Mojca Indihar Stemberger, Jurij Jaklič, Mirjana Kljajic Borštnar, Monika Klun, Andrej Kovačič, Nives Kreuh, Marjan Krisper, Robert Leskovar, Luka Pavlič, Aleš Popovič, Uroš Rajkovič, Vladislav Rajkovič, Živa Rant, Andrej Robida, Niko Schlamberger, Marina Trkman, Peter Trkman, Tomaž Turk, Mirko Vintar, Borut Werber, Boštjan Žvanut, Marko Hölbl Tehnični urednik Slavko Žitnik Lektoriranje Mira Turk Skraba (slov.) Marvelingua (angl.) Oblikovanje KOFEIN DIZAJN, d. o. o. Prelom in tisk Boex DTP d. o. o., Ljubljana Naklada 150 izvodov Naslov uredništva Slovensko društvo INFORMATIKA Uredništvo revije Uporabna informatika Litostrojska cesta 54, 1000 Ljubljana www.uporabna-informatika.si Revija izhaja četrtletno. Cena posamezne številke je 20,00 EUR. Letna naročnina za podjetja 85,00 EUR, za vsak nadaljnji izvod 60,00 EUR, za posameznike 35,00 EUR, za študente in seniorje 15,00 EUR. V ceno je vključen DDV. Revija Uporabna informatika je od številke 4/VII vključena v mednarodno bazo INSPEC. Revija Uporabna informatika je pod zaporedno številko 666 vpisana v razvid medijev, ki ga vodi Ministrstvo za kulturo RS. Revija Uporabna informatika je vključena v Digitalno knjižnico Slovenije (dLib.si). © Slovensko društvo INFORMATIKA Vabilo avtorjem V reviji Uporabna informatika objavljamo kakovostne izvirne članke domačih in tujih avtorjev z najširšega področja informatike v poslovanju podjetij, javni upravi in zasebnem življenju na znanstveni, strokovni in informativni ravni; se posebno spodbujamo objavo interdisciplinarnih člankov. Zato vabimo avtorje, da prispevke, ki ustrezajo omenjenim usmeritvam, pošljejo uredništvu revije po elektronski posti na naslov ui@drustvo--informatika.si. Avtorje prosimo, da pri pripravi prispevka upoštevajo navodila, objavljena v nadaljevanju ter na naslovu http://www.uporabna-informatika.si. Za kakovost prispevkov skrbi mednarodni uredniški odbor. Članki so anonimno recen-zirani, o objavi pa na podlagi recenzij samostojno odloča uredniški odbor. Recenzenti lahko zahtevajo, da avtorji besedilo spremenijo v skladu s priporočili in da popravljeni članek ponovno prejmejo v pregled. Uredništvo pa lahko se pred recenzijo zavrne objavo prispevka, če njegova vsebina ne ustreza vsebinski usmeritvi revije ali če članek ne ustreza kriterijem za objavo v reviji. Pred objavo članka mora avtor podpisati izjavo o avtorstvu, s katero potrjuje originalnost članka in dovoljuje prenos materialnih avtorskih pravic. Nenaročenih prispevkov ne vračamo in ne honoriramo. Avtorji prejmejo enoletno naročnino na revijo Uporabna informatika, ki vključuje avtorski izvod revije in se nadaljnje tri zaporedne številke. S svojim prispevkom v reviji Uporabna informatika boste prispevali k širjenju znanja na področju informatike. Želimo si čim več prispevkov z raznoliko in zanimivo tematiko in se jih že vnaprej veselimo. Uredništvo revije Navodila avtorjem člankov Članke objavljamo praviloma v slovenščini, članke tujih avtorjev pa v angleščini. Besedilo naj bo jezikovno skrbno pripravljeno. Priporočamo zmernost pri uporabi tujk in -kjer je mogoče - njihovo zamenjavo s slovenskimi izrazi. V pomoč pri iskanju slovenskih ustreznic priporočamo uporabo spletnega terminološkega slovarja Slovenskega društva Informatika Islovar (www.islovar.org). Znanstveni članek naj obsega največ 40.000 znakov, strokovni članki do 30.000 znakov, obvestila in poročila pa do 8.000 znakov. Članek naj bo praviloma predložen v urejevalniku besedil Word (*.doc ali *.docx) v enojnem razmaku, brez posebnih znakov ali poudarjenih črk. Za ločilom na koncu stavka napravite samo en prazen prostor, pri odstavkih ne uporabljajte zamika. Naslovu članka naj sledi za vsakega avtorja polno ime, ustanova, v kateri je zaposlen, naslov in elektronski naslov. Sledi naj povzetek v slovenščini v obsegu 8 do 10 vrstic in seznam od 5 do 8 ključnih besed, ki najbolje opredeljujejo vsebinski okvir članka. Pred povzetkom v angleščini naj bo se angleški prevod naslova, prav tako pa naj bodo dodane ključne besede v angleščini. Obratno velja v primeru predložitve članka v angleščini. Razdelki naj bodo naslovljeni in oštevilčeni z arabskimi številkami. Slike in tabele vključite v besedilo. Opremite jih z naslovom in oštevilčite z arabskimi številkami. Vsako sliko in tabelo razložite tudi v besedilu članka. Če v članku uporabljate slike ali tabele drugih avtorjev, navedite vir pod sliko oz. tabelo. Revijo tiskamo v črno-beli tehniki, zato barvne slike ali fotografije kot original niso primerne. Slik zaslonov ne objavljamo, razen če so nujno potrebne za razumevanje besedila. Slike, grafikoni, organizacijske sheme ipd. naj imajo belo podlago. Enačbe oštevilčite v oklepajih desno od enačbe. V besedilu se sklicujte na navedeno literaturo skladno s pravili sistema APA navajanja bibliografskih referenc, najpogosteje torej v obliki (Novak & Kovač, 2008, str. 235). Na koncu članka navedite samo v članku uporabljeno literaturo in vire v enotnem seznamu po abecednem redu avtorjev, prav tako v skladu s pravili APA. Več o sistemu APA, katerega uporabo omogoča tudi urejevalnik besedil Word 2007, najdete na strani http://owl.english.purdue.edu/owl/resource/560/01/. Članku dodajte kratek življenjepis vsakega avtorja v obsegu do 8 vrstic, v katerem poudarite predvsem strokovne dosežke. 88 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI POGLED V ZGODOVINO B Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU Janez Grad Univerza v Ljubljani janez.grad@siol.com 1 PROCES IN ORGANIZIRANOST V proces računalništva in informatike sem bil vključen od 1960 dalje, ko sem se zaposlil na Nuklearnem institutu »Jožef Stefan« v Ljubljani, torej od samega začetka uporabe računalnikov v slovenskem gospodarstvu ter raziskovalni in pedagoški sferi, s poudarkom na Univerzi v Ljubljani, v nadaljevanju Univerza, in Nuklearnem institutu Jožef Stefan, v nadaljevanju NIJS in kasneje IJS. Tako v nadaljevanju podajam informacije, za katere menim, da so potrebne za uravnotežen prikaz razvoja računalništva in informatike v Sloveniji. Vsekakor so bili v 60-tih letih prejšnjega stoletja največji igralci na eni strani Intertrade, ki je pokrival precejšen del poslovne sfere z IBM tehnologijo, na drugi strani pa Univerza v Ljubljani, v okviru katere je bil iniciator in nosilec aktivnosti predvsem NIJS, ki se je v ta namen povezala z ZP Iskro, Izvršnim svetom SRS, oziroma Republiškim zavodom za statistiko, Raziskovalno skupnostjo in Izobraževalno skupnostjo Slovenije, kot glavnima financerkama Univerze in raziskovalne sfere. NIJS je za svoje raziskovalne potrebe najprej uporabljal računalnik IBM 705 na Zveznem zavodu za statistiko v Beogradu, v letu 1963 pa sta Inštitut za matematiko, fiziko in mehaniko Univerze v Ljubljani (IMFM) in NIJS, tedaj še kot inštitut izven Univerze, prenesla obdelave na skupni računalnik ZUSE-Z-23, ki so ga postavili v Ljubljani v sodelovanju z ZP Iskro, ki je prešla na licenčno izdelavo tovrstnih računalnikov. V tem času so univerzitetni raziskovalci in raziskovalci na NIJS sodelovali z Iskro pri razvoju sistemske programske opreme za njene računalnike, ki jih je izdelovala po licenci s firmo ZUSE iz Nemčije. Zaradi hitrega razvoja zmogljivejše računalniške strojne in sistemske programske opreme, ki je bila, vsaj v Sloveniji, konec 60-tih let še predvsem paketno usmerjena, brez možnosti daljinskega pristopa s pomočjo terminalne opreme, in za posamezno institucijo ali podjetje predraga in potratna (saj ne bi bila polno izkoriščena), so Univerza v Ljubljani, vključno z IJS, ZP Iskra in Izvršni svet SRS leta 1968 ustanovili Republiški računski center (RRC), v njegovem okviru pa Operativni elektronski računalniški center (OERC), ki je deloval kot enota IJS pod vodstvom J. Grada. Veliki računalnik v OERC, najprej CDC 2100 nato pa CDC 3300, je bil nameščen v zgradbi Iskre v Stegnah. Zaradi oddaljene lokacije OERC od fakultet je Univerza za pedagoške potrebe nabavila še računalnik IBM 1130, ki je bil postavljen na Inštitutu za matematiko, fiziko in mehaniko. Za koordinacijo dela med visokošolskimi zavodi, IJS in RRC je Univerza v Ljubljani leta 1971 ustanovila Računalniški center Univerze v Ljubljani(RCU), vodja dr. Janez Grad, za poslovno sodelovanje Univerze z IJS in RRC je skrbel Poslovni odbor RCU, za strokovni razvoj računalništva in informatike na Univerzi (v okviru vseh članic univerze) pa je bil ustanovljen Strokovni svet za računalništvo, ki ga je vodil prof. dr. Jernej Virant. Seveda pa so članice Univerze za lastne potrebe poleg skupne računalniške opreme v RRC uporabljale tudi manjše nepovezane računalnike, ki jih tu ne omenjam. Ker so potrebe po računalniških obdelavah hitro naraščale, je RRC leta 1971 nabavil nov, mnogo zmogljivejši računalnik CDC CYBER 72, ki je zagotavljal dostop do centralnega sistema preko oddaljenih terminalov. Novi začasni direktor centra je postal dr. Edo Pirkmajer, ki sta mu sledila Cveto Trampuž in dr. Desan Justin. Za boljšo izkoriščenost novega sistema je RRC vključeval vedno nove uporabnike iz 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 89 Janez Grad: Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU gospodarstva, kot so na primer bile Ljubljanske mlekarne, gradbeno podjetje Obnova, Narodna banka Slovenije, Republiška družba za ceste, Državna založba Slovenije in še drugi. RRC je deloval kot nekakšna »zadruga« partnerjev, ki jih je bilo leta 1977 kar 23, večinoma gospodarskih organizacij. Na centralni računalniški sistem je bilo vezanih 33 terminalov iz raznih krajev Slovenije, nekaj pa tudi izven nje. Zaradi naraščajočih specifičnih potreb množičnega študentskega dela več kot 20.000 študentov na fakultetah in akademijah po hkratnem interaktivnem delu na centralnem računalniškem sistemu je RCU v letu 1981 načrtal novo računalniško mrežo po članicah univerze. CYBER računalnik v ta namen ni bil najbolj primeren, zato se je Univerza odločila za prehod na računalnike firme DEC. Izbran je bil sistem DEC system-10 z vozliščnimi računalniki DELTA ter terminali KOPA 1000 in LA 34. V naslednjih letih je bil sistem še razširjen in tudi dokončno vzpostavljen. Vodja RCU je postal Franc Mandelc. Nov korak na področju računalništva je Univerza napravila v letih 1987-88, ko je iztrošeni DEC 10 zamenjala z dvema računalnikoma VAX 8550, na katera je bilo priključenih preko 200 terminalov in osebnih računalnikov. Preko JUPAK sistema, ki so ga omogočale jugoslovanske PTT organizacije , je bil univerzitetni računalniški sistem povezan z drugimi računalniki v Sloveniji, Jugoslaviji in Evropi, kar je zagotavljalo neposredno izmenjavo informacij z univerzami doma in po svetu v obliki elektronske pošte (BITNET, COSINE) ali s pomočjo vzdrževanja in uporabe skupnih baz podatkov. 2 RABA RAČUNALNIŠKE TEHNOLOGIJE RRC NA UNIVERZI IN IJS V OKVIRU NJIHOVIH STROKOVNIH DEJAVNOSTI Računalniški sistem v RRC je predstavljal najzmo-gljivejšo računalniško tehnologijo Slovenije v svojem času. Z združitvijo njegove uporabe pri vseh njegovih partnerjih je bil to za slovensko družbo edini še dosegljiv način nakupa tako zmogljive računalniške opreme. Partnerji so uporabljali sistem za zadovoljevanje svojih informacijskih potreb v okviru snovanja, kreiranja in rabe lastnega informacijskega sistema. Univerza in IJS sta ga uporabljala kot informacijsko tehnologijo v raziskovalnem in pedagoškem procesu, ter tudi za potrebe upravljanja. To je njihovim pedagoškim delavcem in raziskovalcem omogočilo kreativno delo pri opravljanju svojih osnovnih na- log in zadolžitev, tudi pisanju učnih gradiv, kot tudi aktivno sodelovanje v okviru strokovnih združenj in podjetij doma in v tujini; doma na primer v Slovenskem društvu Informatika, Društvu matematikov, fizikov in astronomov Slovenije, Društvu ekonomistov Ljubljana, ISKRI - Zavod za avtomatizacijo, ISKRI DELTA, INTERTRADE TOZD zastopstvu IBM itd. in v tujini na primer v IFIP. Vse to delo je opisano in predstavljeno v mnogih učbenikih, strokovnih revijah, zbornikih, monografijah in drugih publikacijah. V ilustracijo navajam v nadaljevanju nekaj virov, v katerih so predstavljeni rezultati dela ali pa so opisane dejavnosti določenih skupin raziskovalcev ali raziskovalnih institucij: - FIZIKALNI PRORAČUNI ZA YEGGR (preliminarna konceptna študija nuklearne centrale ...). Nuklearni institut »Jožef Stefan« Reaktorski oddelek NIJS, Ljubljana, oktober 1962. Nosilec naloge dr. ing. M. Osredkar, 8 sodelavcev; študija vsebuje računalniški program za računalnik IBM 705 v Beogradu, avtor J. Grad. - Zbornik del V. jugoslovanskega mednarodnega simpozija o obravnavanju podatkov FCIP/Proce-edings of the Vth yugoslav international symposium on information processing, Bled, 8. - 11. oktober 1969. Ur. odbor: Jernej Virant, Marjan Špegel; tehn. ur.: Andrej Jerman-Blažič; Zvezni strokovni odbor za obravnavanje podatkov/The Federal Professional Committee for Information Processing, Jamova 39, Ljubljana. Preko 80 referatov. Opomba: To je le eden od zbornikov, ki so izšli v več zaporednih letnih srečanjih FCIP. - ŠTUDIJSKO GRADIVO IV Osnove za avtomatsko obdelavo podatkov v javni upravi in družbenih službah. Ur.: dr. Lovro Šturm, Inštitut za javno upravo in delovna razmerja pri Pravni fakulteti v Ljubljani, Ljubljana, november 1969. Posvetovanje: OSNOVE ZA AVTOMATSKO OBDELAVO PODATKOV V JAVNI UPRAVI, Ljubljana, november 1969. 9 referatov ter 5 informacij in prikazov. - (1) Študija o obravnavanju informacij v Sloveniji, (2) Program projekta za obravnavanje informacij pri SKB. Fakulteta za elektrotehniko v Ljubljani, Ljubljana, 1970, 25 avtorjev. - IJS Institut Jožef Stefan Ljubljana Yugoslavia. Published by the Jožef Stefan Institute, Ljubljana, July 1970. 90 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Janez Grad: Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU - ELEKTRONSKI RAČUNALNIKI, osnove-pro-gramiranje-uporaba. Ur.: Franc SPILLER-MUYS, Elektrotehniška zveza Slovenije, Ljubljana 1971. 26 avtorjev. Izdano ob KONGRESU IFIP 71 ( IFIP CONGRESS 71, International Federation for Information Processing) v Ljubljani. - RAČUNALNIŠTVO - Gradivo s tečaja za srednješolske profesorje. Ur.: B. Roblek, Zavod za šolstvo SR Slovenije, Ljubljana, 1972. 7 avtorjev. - POROČILO O DELU INSTITUTA V LETU 1971. Ur.: Andrej Šmalc, Univerza v Ljubljani INSTITUT »JOŽEF STEFAN« LJUBLJANA, JUGOSLAVIJA. IJS POROČILO P-278, Letno poročilo, april 1972. - BILTEN UIVERZE V LJUBLJANI, RAČUNALNIŠTVO, 1971 - 1977. Za strokovni svet prof. dr. J. Virant, za RCU doc. dr. J. Grad. - SISTEM ZA OBRAVNAVANJE DOKUMENTACIJSKIH INFORMACIJ RAZLIČNIH BAZ PODATKOV - I. faza. ISKRA - Zavod za avtomatizacijo Ljubljana, 1973, Poročilo raziskovalne naloge, nosilec naloge Vera Mirt - Levovnik, 6 sodelavcev. - slovenija paralele 23, ,73, GOSPODARSKO-DRUŽ-BENA REVIJA. Glavni ur.: Lojze Jakopič, odgovorni ur.: Mihajlo Milanovic, tehnični ur.: Sašo Mirtič. EPID-BIRO ZA EKONOMSKO PROPAGANDO IN ZALOŽNIŠKO DEJAVNOST, Ljubljana, Hala Tivoli, Celovška 25. - INFORMATICA 73, Zbornik 8. jugoslovanskega mednarodnega simpozija o obravnavanju podat-kov/Proceedings of the 8th yugoslav international Symposium on information processing, Bled 1. -5. oktober 1973. Ur. odbor: Anton P. Železnikar, Iztok Lajovic; tehn. ur.: Andrej Jerman-Blažič; Zvezni strokovni odbor za obravnavanje podatkov, Jamova 39, Ljubljana. Preko 100 referatov. Opomba: To je le eden od zbornikov, ki so izšli v več zaporednih letnih srečanjih INFORMATICA. - RAZISKOVALEC, Let. 4, Št. 3, str. 79 - 103, Ljubljana, marec 1974. Informativni bilten, izdaja RSS s sodelovanjem SAZU, Zavoda SRS za mednarodno Tehnično sodelovanje in Zveze raziskovalnih organizacij Slovenije. - Ivan Bratko, Vladislav Rajkovič (1974): UVOD V RAČUNALNIŠTVO. Državna založba Slovenije, Ljubljana 1974. - Janez Grad (1975): The experience of operating the University Computing Centre with other users. Sperry Univac International Executive Centre, COMPUTERS IN EDUCATION AND RESEARCH Symposium, Rome, Nov. 18-20, 1975. - ORGANIZACIJA INFORMACIJSKEGA CENTRA I - III. Poročilo o raziskovalnem delu, Računalniški center Univerze v Ljubljani, 1975, 1976, 1978. Nosilec naloge dr. Janez Grad, preko 14 sodelavcev iz podjetij in ustanov v Sloveniji. - SREDNJEROČNI PLAN RAZVOJA RAČUNALNIŠKEGA SISTEMA UNIVERZE V LJUBLJANI 1976-1980. Univerza v Ljubljani RAČUNALNIŠKI CENTER UNIVERZE, Ljubljana, 1977. Podpisniki v publikaciji: 20 pooblaščenih predstavnikov članic Univerze in rektor Univerze. - PRVO DELOVNO POROČILO (december 1976) IN DRUGO DELOVNO POROČILO (november 1980), Komite za družbeno planiranje in informacijski sistem, Delovna skupina za pripravo republiškega programa izobraževanja kadrov za potrebe računalništva in informatiko, Ljubljana. Vodja delovne skupine prof. dr. J. Virant, 13 članov in 7 sodelavcev. - RAZISKOVALEC, Let. 7, Št. 9-10, str. 279 - 352, Ljubljana, september - oktober 1977. - RAČUNALNIŠKA MREŽA UNIVERZE. Univerza Edvarda Kardelja v Ljubljani Računalniški center univerze. Glavni urednik Janez Grad, odgovorni urednik Franc Mandelc. Računalniški center Univerze, Kardeljeva ploščad 17, Ljubljana, 1981. - informatica JOURNAL OF COMPUTING AND INFORMATICS. Editor-in-Chief: Anton P. Žele-znikar, Executive Editor: Rudi Murn; Vol. 6, No. 1, 1982; INFORMATIKA, Slovene Society for Informatics, Ljubljana, Parmova 41, Yugoslavia. YU ISSN 0350-5596 - Matjaž Gams (2014): Editorial: »Michie-Turing« IS2014 Award Recipient: Janez Grad. Informatica An International Journal of Computing and Informatics. Executive Editor - Editor in Chief: Anton P. Železnikar, Executive Associate Editor - Managing Editor: Matjaž Gams, Executive Associate Editor - Deputy Managing Editor: Mitja Luštrek, Executive Associate Editor - Technical Editor: Drago Torkar; Vol. 38, No. 4, 2014; Slovene Society Informatika (president Niko Schlamberger), Lito-strojska c. 54, Ljubljana, Slovenia. ISSN 0350-5596 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 91 Janez Grad: Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU - PC LIP in PC LIP+ programski paket za linearno programiranje. INTERTRADE TOZD Zastopstvo IBM, Center za razvoj programske opreme, UNIVERZA V LJUBLJANI Ekonomska fakulteta, Fakultetni center za informatiko, razvoj in prodaja programske opreme, 1986-87, nosilec naloge dr. Janez Grad, 2 sodelavca. - Dr. Ivan Turk s sodelavci (1987): POJMOVNIK POSLOVNE INFORMATIKE. Izdalo Društvo ekonomistov Ljubljana v sodelovanju z Iskra Delta Ljubljana, Založilo Društvo ekonomistov Ljubljana Trubarjeva 3, Ljubljana1987. (Dr. Ivan Turk in 37 strokovnih sodelavcev). - ZBORNIK LJUBLJANSKE UNIVERZE 1989. Gl. in odg. Ur.: Alenka Štih; Univerza Edvarda Kardelja v Ljubljani, Ljubljana 1989. - RAČUNALNIŠKI SLOVARČEK angleško-sloven-ski, slovensko-angleški, 3. razširjena izdaja. Strokovni urednik Matjaž Gams, 9 nacionalnih koordinatorjev slovenskega računalniškega izrazoslovja in 80 sodelavcev. CANKARJEVA ZALOŽBA, LJUBLJANA 1993. ISBN 86-361-0822-5 - uporabna INFORMATIKA. Gl. in odg. ur.: Mirko Vintar, tehn. ur.: Katarina Puc Let. 1, Štev. 1, jul/ avg/sept, 1993; Slovensko društvo Informatika, Ljubljana, Vožarski pot 12, Slovenija. Opomba: Revija še vedno redno izhaja pod naslovom UPORABNA INFORMATIKA. ISSN 1318-1882. Vmesna urednika sta bila: odg. ur.: Jurij Jaklič, tehn. ur.: Mira Turk Škraba; sedanja urednika pa sta: glavni ur.: dr. Saša Divjak, tehn. ur.: dr. Slavko Žitnik. - SOR, 93 SIMPOZIJ IZ OPERACIJSKIH RAZISKAV, 93, Ljubljana, 25. - 27. november 1993. ZBORNIK DEL, 1993. Urednika: prof. dddr. Viljem Rupnik, prof. ddr. Ludvik Bogataj; Slovensko društvo Informatika (SDI) Sekcija za operacijske raziskave (SOR), Ljubljana, Vožarski pot 12. UDK: 519.8(08). Opomba: Sekcija za operacijske raziskave še vedno organizira simpozije in izdaja zbornike del, sedaj pod naslovom, na primer v letu 2007: - Proceedings of the 9th International Symposium on OPERATIONAL RESEARCH SOR ,07 in Slovenia, Nova Gorica, Slovenia, September 26-28, 2007. Edited by: L. Zadnik Stirn and S. Drobne, Tech. editor: Samo Drobne; Slovenian Society Informatika - Section for Operational Research, Ljubljana, Vožarski pot 12, Slovenia. ISBN 978-9616165-25-9 - DSI DNEVI SLOVENSKE INFORMATIKE ,94, I. posvetovanje, Portorož Avditorij, 13. - 15. april 1994. ZBORNIK POSVETOVANJA. GZS Združenje za informatiko in računalništvo, Slovensko društvo Informatika, Društvo ekonomistov Ljubljana. Opomba: Slovensko društvo Informatika še vedno organizira posvetovanja in izdaja zbornike posvetovanja s spremenjenim naslovom, na primer v letu 2001: - DSI 2001 DNEVI SLOVENSKE INFORMATIKE 2001/SLOVENIAN INFORMATICS CONFERENCE 2001, Portorož, Slovenija, 18. - 21. april 2001. ZBORNIK POSVETOVANJA/PROCEEDINGS. Odgovorni urednik, editor-in-chief: Janez Grad; Slovensko društvo Informatika/Slovenian Society Informatika, Ljubljana 2001. ISBN 961-6165-11-9 - PRIPOVEDI O IJS - OB 50-LETNICI INSTITUTA »JOŽEF STEFAN«. Ur.: prof. dr. Milan Osredkar in Natalija Polenec, univ. dipl. arh.; Institut »Jožef Stefan«, Jamova 39, Ljubljana, sept. 2000. ISBN 961-6303-21-X - 90 let Univerze v Ljubljani Med tradicijo in izzivi časa 1919- 2009. Ur.: Jože Ciperle; Ljubljana: Univerza 2009. Delo, 30. november 2009: Sprehod skozi čas ... - Publikacije Centra za programirano učenje, Ljubljana. Predstojnica centra: prof. dr. Aleksandra Kornhauser. - FRI 20: 20 let Fakultete za računalništvo in informatiko Univerze v Ljubljani. Fakulteta za računalništvo in informatiko. Univerza v Ljubljani, Večna pot 113, Ljubljana, 2016. ISBN 978-961-6209-92-2 3 MEDNARODNO SODELOVANJE Seveda pa so bili Univerza, IJS in druge raziskovalne institucije ves čas dejavne tudi v mednarodnem okviru. Izpostavljam mednarodna projekta COST 11 in COST 12. 4 PROJEKTI COST V okviru mednarodnega sodelovanja Jugoslavije z Evropsko gospodarsko skupnostjo (EGS) in drugimi 92 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Janez Grad: Razvoj računalništva in informatike na Univerzi v Ljubljani, s poudarkom na pomenu RRC in RCU državami na področju znanstvenih in tehnoloških raziskav se je Slovenija vključila v več multilateralnih projektov. Vključitev je potrdila na ministrski konferenci v Bruslju leta 1971. Skupaj z 18 evropskimi državami se je tako vključila tudi v multilateralno sodelovanje na področju znanstvenih in tehnoloških raziskav - COST (Cooperation scientifique et technique). Na mednarodnem področju je sodelovanje Jugoslavije potekalo preko Zveznega zavoda za mednarodno znanstveno, prosvetno-kulturno sodelovanje v Beogradu, sodelovanje znotraj Slovenije in Slovenije na medrepubliškem nivoju pa je koordinirala Komisija za mednarodno znanstveno sodelovanje pri Raziskovalni skupnosti Slovenije. (Janez GRAD, Janez ROGELJ (1977): SODELOVANJE JUGOSLAVIJE Z EVROPSKO GOSPODARSKO SKUPNOSTJO IN DRUGIMI DRŽAVAMI NA PODROČJU ZNANOSTI IN TEHNOLOGIJE. Raziskovalec 7 (1977) 9-10. Za področje računalništva in informatike sta bila zanimiva predvsem projekta COST 11 in COST 12. Projekt COST 11 - Evropska mreža informatike. Cilj projekta je bil povezati med seboj v mrežo pet nacionalnih računalniških centrov, kot vozlišč mreže, ki naj bi služila kot model za možno kasnejšo evropsko računalniško mrežo. Kot vozlišča mreže so bili določene države Vel. Britanija, Francija, Italija, Švica in Norveška. Ostale države, članice na projektu, med njimi tudi Jugoslavija, so sodelovale pasivno. To pomeni, da same niso vršile raziskav, imele so pa pravico dostopa do vseh informacij in rezultatov projekta (prototip opreme, programska oprema, ...). Projekt je bil petleten in se je iztekel leta 1978. Zvezni koordinator v Jugoslaviji je bila Raziskovalna skupnost Slovenije, ki je bila, tako kot Univerza v Ljubljani, vključno z IJS, partner v RRC. Kot predstavnika v projektu sta sodelovala dr. Edo Pirkmajer, ki je bil dvakrat zapored izbran za predsednika, in dr. Tomaž Kalin; za-pažena je bila velika aktivnost obeh jugoslovanskih predstavnikov. Naloga naših raziskovalcev je bila, da skrbno proučijo dobljene izsledke in jih uporabijo pri načrtovanju domače jugoslovanske mreže računalnikov. Načrtovane so bile tudi vrste informacij, ki naj bi se prenašale preko evropske računalniške mreže. Projekt COST 12 - Evropska programska knjižnica. Cilj projekta je bil formiranje programskih knjižnic v državah, ki so sodelovale na projektu. Za projekt je bilo v Jugoslaviji veliko zanimanje. Za zveznega koordinatorja je bila izbrana Raziskovalna skupnost Slovenije, strokovna in tehnična dela pa naj bi za njo opravljal Računalniški center Univerze v Ljubljani, vodja dr. Janez Grad. Zaradi medsebojnih nesoglasij članic na projektu, predvsem Anglije in Francije, kje naj bi stal evropski informacijski center, je projekt zastal. ■ Janez Grad je leta 1958 diplomiral iz matematike na Naravoslovni fakulteti Univerze v Ljubljani, leta 1968 je magistriral iz matematične fizike na Univerzi v Birminghamu, leta 1973 pa doktoriral iz matematičnih znanosti na Vseučilišču v Zagrebu. Po letu 1957 je bil strokovni sodelavec na Institutu Jožef Stefan, vodja Republiškega računskega centra in predstojnik Računalniškega centra Univerze v Ljubljani. Od leta 1973 do leta 1999 je sodeloval kot učitelj za informatiko na Ekonomski fakulteti Univerze v Ljubljani, nato pa je do upokojitve leta 2007 poučeval informatiko na Fakulteti za upravo Univerze v Ljubljani. Strokovno se je izpopolnjeval na Zveznem zavodu za statistiko v Beogradu, Institutu für Strahlen und Kernphysik v Bonnu, Univerzi v Birminghamu, kot gostujoči profesor pa je delal na Univerzi v Indiani, School of Business, Bloomington, ZDA. Ukvarjal se je s programiranjem na računalniku in z numerično matematiko - reševanjem problema lastnih vrednosti in vektorjev matrik; v zadnjih letih pred upokojitvijo pa se je ukvarjal predvsem z reševanjem problemov s področja operacijskega raziskovanja in s področja baz podatkov. Je soavtor šestnajstih monografij, učbenikov in knjig, 119 člankov in referatov v strokovnih revijah ter zbornikih strokovnih srečanj doma in v tujini ter 38 poročil raziskovalnih nalog in projektov. Opravil je več recenzij člankov za domače in tuje revije, bil je član številnih domačih in tujih strokovnih združenj in zvez ter član uredniških odborov več domačih in tujih strokovnih revij. Slovensko društvo INFORMATIKA mu je leta 1995 podelilo priznanje za življenjsko delo na področju razvoja in uveljavitve informatike v Sloveniji. Bil je mentor pri dvanajstih doktorskih disertacijah, več deset magisterijih in univerzitetnih diplomah na ekonomski fakulteti. Univerza v Ljubljani mu je za njegovo delo podelila zlato plaketo in naziv zaslužni profesor; na 17. mednarodni multikonferenci Informacijska družba so mu podelili nagrado Donald Michie and Alan Turing za življenjsko delo. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 93 ZNANSTVENI PRISPEVKI B A usability comparison of input devices for precise and intuitive interaction with 3D visualizations Uporabniška primerjava vhodnih naprav za natančno in intuitivno interakcijo v 3D vizualizacijah Ciril Bohak1, Jože Guna2, Peter Škrij3, Alja Isakovic4, Matija Marolt1 1University of Ljubljana, Faculty of Computer and Information Science, Večna pot 113, 1000 Ljubljana 2University of Ljubljana, Faculty of Electrical Engineering, University of Ljubljana, Tržaška cesta 25, 1000 Ljubljana 3University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies, Glagoljaška 8, 6000 Koper 4Cofound.it One, informacijske tehnologije, d.o.o., Kersnikova ulica 10, 1000 Ljubljana ciril.bohak@fri.uni-lj.si; joze.guna@fe.uni-lj.si; peter.skrlj92@gmail.com; alja.isakovic@gmail.com; matija.marolt@fri.uni-lj.si Abstract The paper presents a user study comparing the performance and usability of different input devices for precise manipulation of 3D objects: a regular mouse, a 3D mouse, and the gesture-based Leap Motion Controller. We show that the 3D mouse is well suited for the task as it yielded the lowest rotation error rate and best overall usability while tasks were completed with the 3D mouse as quickly as with the regular mouse interface. The 3D mouse earned an average System Usability Scale score of 88.7, the regular mouse 72.4, however, the Leap Motion Controller was barely suitable for the task, receiving an average System Usability Scale score of 56.5. The study showed that users needed the most time to finish the tasks with the Leap Motion Controller and that its gestures were not as easy to learn compared to the 3D mouse. This led us to conclude that the 3D mouse is currently the best input option among the tested devices for 3D tasks that require both high precision, quick completion and a fast learning curve. Keywords: User experience; usability evaluation; user study; 3D manipulation; natural user interfaces; 3D mouse. Izvleček Članek predstavlja uporabniško študijo, ki primerja uspešnost in uporabnost različnih naprav za natančno manipulacijo s 3D objekti: običajno računalniško miško, 3D miško in vmesnik Leap Motion, ki temelji na uporabi kretenj. Pokazali smo, da je 3D miška zelo primerna za takšna opravila, saj so z njo uporabniki dosegli najmanjše napake v rotaciji, hkrati pa je dosegla najvišjo oceno za uporabniško izkušnjo. Uporabniki so izvedli opravila enako hitro kot z običajno miško. 3D miška je dosegla v povprečju oceno 88,7 na lestvici System Usability Scale, običajna miška je dosegla 72,4, vmesnik Leap Motion pa 56,5. Med rezultati študije se izkazalo, da uporabniki največ časa za naloge porabijo z uporabo vmesnika Leap Motion, in da se njegove uporabe niso priučili tako hitro kot uporabe 3D miške. Zaključek študije je, da je 3D miška trenutno najbolj primerna vhodna naprava med testiranimi za opravila v 3D okolju, ki potrebujejo tako natančnost, hitrost in se je njihove kot hitro učno krivuljo. Ključne besede: uporabniška izkušnja; uporabniko ovrednotenje; uporabniška študija; 3D manipulacija; naravni uporabniški vmesniki; 3D miška 94 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations 1 INTRODUCTION The traditional computer mouse made desktop computers more accessible to millions of users by offering an easy-to-learn input method for the »point--and-click« graphical user interfaces (GUI) based on the WIMP (»window, icon, menu and pointing device«) paradigm (van Dam, 1997). WIMP GUIs were designed and optimized for 2D document-based applications, but create a greater »cognitive distance« when 3D objects are introduced (van Dam, 1997). And while professional 3D computer-aided- design (CAD) users have been successfully using mouse and keyboard input for 3D navigation and manipulation, it is an interaction method that requires a high level of learning, practice and abstraction. As interactive 3D content is becoming commonplace in a wide range of fields, the mouse input method might not offer the best choice for casual users who still require a certain level of precision and ease of use, but cannot afford to spend a lot of time learning a new user interface of a 3D application. And while there are already several alternative input devices that were designed for post- WIMP style of interaction, they are mostly used in specialized fields (e.g., 3D mice used by CAD professionals) or with gaming consoles (e.g., the motion sensing Microsoft Kinect), which means that they are still highly unfamiliar to most users. Therefore, the question is whether any of the alternative input devices that were designed for 3D interaction can be learned more easily by beginners than the already familiar (yet not optimized for 3D) mouse. Visualization of 3D datasets is a good example of an application requiring users to interact with data in 3D space in different ways. Most of user interaction tasks can be divided into navigation, selection/manipulation and system control (Bowman et al., 2001). The 2D nature of the computer screen on which the 3D dataset is projected makes both viewpoint navigation and object manipulation essential in order for the user to fully and effectively grasp the presented data. Therefore, 3D desktop applications have to support a wide range of camera movements that navigate around 3D objects (Rotate-Pan-Dolly) and techniques for manipulating 3D objects (Rotate-Scale- Translate) (Jankowski and Hachet, 2015). All of the above-mentioned aspects are important while developing a highly usable interface for 3D interaction. For us, the problem of choosing the best input method for 3D interaction, both in terms of precision and usability, arose when we developed NeckVeins (Bohak et al., 2013), a medical visualization platform. NeckVeins displays 3D vascular models of patients (Figure 1), captured with computed tomography (CT) or other volumetric methods (e.g., MRI or ultrasound). The application is used by medical professionals to explore the 3D data from different viewpoints. Figure 1: The user interface of the NeckVeins application 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 95 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations Since the application was developed for medical purposes, it is essential that navigation in 3D space is intuitive and easy to use, while still offering high precision. An additional requirement for the application was that it should work with existing hardware, so we explored inexpensive input devices that are already on the market and that can easily be plugged into existing systems, and excluded alternatives like multi-touch that require more expensive system upgrades. This led us to implement three different modes of interaction with the following input devices: ■ a regular mouse that users are already familiar with. The mouse is used for object manipulation. Zoom functionality is implemented in discrete steps due to the nature of the mouse wheel design; ■ a 3D mouse (3Dconnexion Space Navigator1), which builds on the familiarity and popularity of a computer mouse, but adds six-degrees of freedom (6-DOF -movements along three world axes and rotations around them) for intuitive and precise 3D navigation. 6-DOF in comparison with regular mouse which offers weo-degrees of freedom offers wider range of input actions. Users can toggle between control of the object and control of the camera by pressing one of the buttons on the 3D mouse, thus performing navigation and manipulation tasks with same device. In our application, we can adjust the sensitivity of interactions as well as toggle between using the dominant movement/rotation (rotation or movement along individual axis) or all of them; ■ a Leap Motion Controller2, which offers a touchless, gesture-based natural user interface (NUI). The Leap Motion Controller tracks the 3D position and orientation of hands and fingers in the space above the device. We linked the position and orientation of hands to object rotation and zoom. We have not implemented camera movement functionality for the Leap Motion Controller due to complexity introduced by additional gestures. Interaction with the Leap Motion Controller starts by opening the palm and ends by closing it. Scaling and rotations are bound to hand movements. In our application, we can adjust the sensitivity of movements detected by the device. 1 https://www.3dconnexion.eu 2 https://www.leapmotion.com The rest of the paper is organized as follows: following the introduction, related work is presented in Section 2. The user study research method and hypotheses are presented in Section 3. Results of the user study are described, analyzed and discussed in Sections 4 and 5, respectively. Finally, key conclusions are drawn in Section 6. 2 RELATED WORK A lot of Human-Computer Interaction (HCI) research that compares different input devices focuses on input speed by measuring the time it takes to complete the task and the error rate during the task, which are both easy to measure and compare directly. That was also the case in one of the first user studies on input devices conducted in 1967, which found the computer mouse to be the most accurate of all studied devices, but not the fastest (Ortega et al., 2016). Ivan Sutherland's light pen was slightly faster than the mouse, but it had a greater error rate and caused discomfort during prolonged use. This user study sets a good example of how utility, the device's feature set, is not enough without usability, which describes how easy and pleasant it is for the users to use the features of the devices (Nielsen, 2012). Other authors have also showed that interaction science is well established and needed (Pike et al., 2009). The usability aspect is commonly measured and compared with standardized questionnaires like the System Usability Scale (SUS). The SUS was introduced in 1986 by John Brooke (1996) and is still one of the most widely used standard usability tools, especially because of its versatility, reliability and simplicity aspects. The SUS questionnaire consists of 10 questions, half of them worded negatively and half positively towards the usability aspects of the system under test. For each question the participants can rate how strongly they agree with the specific question on a 5-point Likert scale. The final result of the SUS questionnaire is a score on a scale from 0 (negative) to 100 (positive) (Bangor et al., 2009), which can be used to compare results across different user studies. In terms of user performance, a lot of research on input devices focuses on pointing tasks, based on Fitt's law. And while pointing and selection is also part of 3D interaction, especially in virtual environments (Teather and Stuerzlinger, 2010), studies on 3D interaction often include tasks that mirror real-world applications. A common task is 3D docking, 96 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations in which participants aim to match the position, rotation and scale of a sample object in 3D space (Jan-kowski and Hachet, 2015). A good example of a study based on a 3D docking task is the work by Besançon et al. (2016) that evaluated both the performance and usability aspects of 3D data manipulation with a standard mouse, touch input built into the screen, and tangible input using a hand-held cuboctahedron with markers for camera-based 6-DOF 3D tracking. Participants completed the 3D docking task faster with the tangible input, followed by touch and mouse respectively, but none of the techniques provided higher precision than the others. The participants did however feel they had the most precise control using the mouse, followed by the touch interface. And while the participants preferred the novel tangible interface overall, the authors concluded that each input method has its own advantages and limitations that have to be considered while making a choice. Other usability studies on touch input focus mostly on 3D navigation in map applications, but Yu et al. (2010) compared a touch interface with mouse interaction on different 3D scientific visualizations. They found the touch interface to be as good as the mouse in terms of speed, easy to learn and preferred by participants for exploration and wayfinding. Bade et al. (2005) compared different mouse-based interaction techniques for predictable 3D rotations in 3D radiological visualizations. The study shows that the three input modalities provide similar levels of precision but require different interaction times. It is more common for 3D interaction studies to include 3D mice and other modified mouse alternatives that were designed with 3D interaction in mind. Perelman et al. (2015) compared the performance of a 3D mouse with the Roly-Poly Mouse (RPM), which combines the positioning abilities of a traditional mouse with rolling and rotating abilities of 3D devices. The study found the RPM faster for 3D pointing, but both performed equally well in the 3D docking task. Similarly, Balakrishnan et al. (1997) evaluated a 4-DOF Rockin' Mouse and found it 30% faster than a standard mouse in a typical 3D interaction task. The Rockin' Mouse was preferred by the participants, especially by expert users, but it did require some practice. Hinckley et al. (1997) also showed that 3D input devices can provide faster 3D rotation than 2D input techniques without sacrificing precision. And while touch interfaces and various mouse modifications with more degrees of freedom appear to be a viable alternative to 2D mouse-based input, gesture-based input shows a lot of potential for users with special needs or environments with specific requirements, even though it is often slower than the traditional mouse. Bhuiyan and Picking (2011) presented a usability evaluation of gesture-based navigation that showed positive results among older and disabled users in terms of ease of use and learning of the system. Coelho and Verbeek (2014) found that the gesture-based Leap Motion Controller performed better than the mouse in single target 3D pointing tasks, but was more time consuming and less precise when multiple targets were introduced. Expert users showed a bias towards the mouse in 3D tasks, but the Leap Motion Controller scored surprisingly high SUS score results despite accuracy issues. Ryu et al. (2011) found that a touchless mouse (similar to the Leap Motion Controller) was about three times slower than a regular mouse, but did not cause significantly more errors in the pointing and selection tasks. The authors concluded that the touchless mouse could be a viable alternative, despite an inferior throughput, in environments like hospital operation rooms, where direct touch can be problematic. Natural touchless user interfaces are a good fit for sterile medical environments. Ebert et al. (2012) describe the use of a Kinect 3D sensor and additional voice commands in a touch-free navigation system for radiological images. The Kinect interaction was slower than the standard mouse input. That was partly due to the lack of familiarity with the gesture-based system and the authors concluded that more training might be needed. Another study tried to tackle the challenge of non-contact navigation with the Leap Motion Controller (Gratzel et al., 2004). They linked hand gestures from the Leap Motion Controller with application key bindings in the GameWave3 application. They obtained good results and also tested the device in a real-life situation during surgery, but their method was not tested from the usability standpoint. Similarly, the Leap Motion Controller was reportedly successfully used during dental surgery to control and consult the surgical plan during the operation, but the authors Rosa and Elizondo (2014), did not perform a usability study. 3 GameWave can be obtained in the Leap Motion Airspace store. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 97 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations Due to specific requirements of medical 3D applications, it is important to further explore the usability and precision of emerging gesture-based interfaces and compare their performance with a familiar alternative (mouse) and specialized 3D input devices (3D mouse) to make sure that precision can be preserved, while still providing an easy-to-learn option that does not cause unnecessary cognitive load during already complicated tasks such as diagnostics and surgery. That is why our presented study considers both aspects to provide recommendations for user-centered 3D input in the medical field and other fields where non-expert users have to control 3D visualizations with precision. 3 METHOD The main goal of this study was to identify which of the tested input devices enables fast and precise interaction with a 3D medical visualization and is also easy to use. We conducted a user study to compare the performance of the devices in terms of speed by measuring completion time and in terms of precision by measuring rotation and zoom error rates. In addition to the performance, the usability of each of the three input devices was also evaluated by giving study participants 3D docking tasks that model some 3D interaction skills used by medical professionals, and by having the participants complete a SUS usability questionnaire for each of the devices. Based on related research findings, we defined the following hypotheses: ■ H1: In terms of time required to complete individual 3D docking tasks, the Leap Motion Controller will be the slowest device, while the mouse and the 3D mouse will not differ significantly. ■ H2: Rotation error rate of all devices will not differ significantly. ■ H3: Zoom error rate of all devices will not differ significantly. ■ H4: All input devices will be suitable for use with the NeckVeins application (SUS score is equal or better than »OK«). ■ H5: The participants will favor the Leap Motion Controller due to its novelty regardless of its performance. 3.1 Participants Even though the NeckVeins application was built for medical professionals, we decided to test its 3D inte- raction and the three chosen input devices on a more diverse group of participants. A total of 29 participants took part in our study, of those 55% men and 45% women. 14 participants were between ages 18 and 24, 11 between ages 25 and 34, 3 between ages 35 and 44, and 1 between 45 and 54 years. Of those, 15 were students, 13 were employed and 1 unemployed. Their professional background was diverse, ranging from technical and natural sciences to medical, humanistic and social areas of expertise. Most of the participants (70%) had no previous experience with the NeckVeins application. More than half of the participants had previous experience and understood the use of the regular computer mouse for 3D object manipulation, but 78% of the participants had no experience with manipulating 3D objects with a 3D mouse. 3.2 Apparatus The user study was performed in a dedicated room where participants were isolated from outside factors such as noise or interruptions, so the same conditions were ensured for all participants. The experiment was conducted on a desktop computer preinstalled with a modified NeckVeins application, which contained different 3D docking tasks that the participants had to complete for each input device modality. In order, not to distract the participants (who were not all medical professionals) with the content of visualizations, the tasks consisted of docking a neutral 3D object (teapot), so that the participants could focus on the 3D manipulation task at hand. One of the 3D docking tasks and the user interface of the testing application is shown in Figure 2. The interaction mappings for the individual devices were implemented as presented in Figure 3. The same setup (shown in Figure 4) was used by all of the participants and each participant was tested with each of the three interaction methods. For the regular mouse test, all participants used a Logitech M90 mouse. The 3D mouse was a 3Dconnexion Space Navigator, and the first generation of the Leap Motion Controller was used. 3.3 Procedure The moderator guided each experimental run using the same test plan for each participant to ensure that all participants performed the same tasks with all three input devices under the same conditions. An 98 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations s ^^ FrUdi % - MJjilu rrle.LMiu.La ptaal«lNhi u intal trn Lir an] a Figure 2: A screenshot of the modified NeckVeins application with a 3D docking task. The participant controls the 3D model of the red teapot on the left and tries to match its rotation and zoom level to the grey teapot model in the right side of the screen. Figure 3: Mappings of the interaction for individual actions and individual devices. observer was also present throughout the experiment. The experimental setup is shown in Figure 3. At the beginning of each experimental run, the participant was asked to sign a participation agreement and an optional video recording consent. The participant was able to refuse video recording to reduce possible stress during the experiment. Next, the participant completed a short entry questionnaire about their demographic information (age and gender), and their previous experience with the tested input devices, 3D object manipulation, and the NeckVeins application. Previous experience was rated on a 5-point Likert scale, »1« indicating no expe- rience/knowledge and »5« indicating full experience/ knowledge. After the questionnaire, the moderator explained the purpose of the study, introduced the test version of the NeckVeins application (Figure 2) and described the goal of the 3D docking tasks that were used in the experiment. The participant was asked to confirm whether they understood the goal of the 3D docking tasks. After the participant confirmed their understanding of the task, the actual experiment begun. For each input device, the procedure was the same. First, the participant was given a description of the device 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 99 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations they would be using in that round. The participant was given 5 minutes to get familiar with the device before starting with the 3D docking tasks. During the familiarization period, any questions regarding the application and the input device were answered by the moderator. After the familiarization period, the testing begun if the participant confirmed that they knew how to use the input device in the application, otherwise the uncertainties were clarified first. This assured a basic level of familiarity before each round of testing. During the test for each device, the participant completed seven 3D docking tasks for each of the three input devices, for a total of 21 tasks per participant. The order of input devices and tasks was randomized for counterbalance. For three devices, this means 6 device order sequences, so we had 4 and 5 repetitions of each device order sequence. The goal of each 3D docking task was to align, in terms of rotation and zoom, a red colored teapot displayed on the left-hand side of the screen (the participant's work area) with a grey colored teapot displayed on the right-hand side of the screen (the task goal). The different colors were selected for immediate distinc- tion between the object of manipulation object and target object. Figure 2 shows a screenshot of the test application. Individual tasks had differently oriented teapots, varying in desired orientation (rotation) and scale (zoom), but the interaction was the same for all seven tasks. The order of the presented input devices and 3D docking tasks was counterbalanced — randomly selected and balanced among the participants. The moderator started each of the 3D docking tasks by selecting one of the predefined tests and starting the timer. The time needed to complete the task, as well as the rotation and zoom error rate of the positioned teapot with respect to the reference teapot were automatically recorded by the test application for each individual task separately from start of the task — when the new task was displayed to the participant — to task completion — when the participant was satisfied with the alignment by pressing the space key on the keyboard. The choice of speed versus precision was left to the participant and the moderator did not interfere during the tasks unless fatigue or distracte-dness were noticed. The observer took notes of the 100 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations participant's body language, actions, comments and any problems that occurred in the test application. In case of an error in the test system or when the participant felt they were unable to complete the task, the system was reset and the participant was allowed to repeat the task. In case of a misunderstanding when performing the task at hand, the experimental run was paused, additional explanation was given to the participant and then the experimental run resumed. If there was a problem with the participant's distraction or tiredness, the experiment was also paused and the participant was given some time before the experiment was resumed. If this was not possible, the participant was removed from the experiment and all the collected data was discarded. The data was continuously recorded throughout the experiment. After the participant finished with all seven 3D docking tasks for an individual input device, they were asked to fill in the SUS questionnaire for that device. The procedure was then repeated for the other two input devices in the same manner. After completing the experiment with all three input devices, the participant was asked additional questions regarding the comparison between individual input devices. The comments and suggestions were written down by the observer. 3.4 Design The independent variable in the user study was the input device used for the task. Three devices were tested in the study: regular mouse, 3D mouse, and the Leap Motion Controller. The measured dependent variables were: completion time measured in seconds, rotation error rate measured in degrees, zoom error rate measured in percentages, and the SUS usability score on a scale from 0 - 100. Completion time was determined by measuring the time needed (in seconds, precision was one second) to complete each individual task for each input device (for each user). The average values and standard deviations were calculated alongside with the shortest and longest time needed to perform the tasks. Rotation error rate was determined by summing the measured errors in rotation compared to the perfect position (in arc degrees (°) around each individual axis (X, Y and Z), measurement precision was 0.01°) of completing each individual task for each input device (for each user). Its minimal - best value is 0° and its maximum - worst value is 540° (180° around each axis). The average values and standard deviations were calculated alongside with the best (lowest) and worst (highest) error rate of all cases. With such metric, it is also possible to check whether rotation error about a certain axis stands out more than others. Zoom error rate determined by measuring the error of zooming compared to the perfect position (in %, measurement precision was 0.01%) for completing each individual task for each input device (for each user). The average values and standard deviations were calculated alongside with the smallest and largest zoom error of all cases. The usability aspect was determined by measuring the SUS score of each input device, using the standard SUS questionnaire (Brooke, 1996; Bangor et al., 2009). To better design the experiment, the study was conducted in two parts. The first part was a pilot study in which we tested 7 participants and evaluated the user study methodology and the test application. The participants from the pilot study were not included in the presented data analysis or in the second part of the study due to the knowledge gained during the trial run. We used the results, comments and responses from the pilot study participants to improve the test plan, questionnaire and the test application. The second part was a comprehensive study with 29 participants and was completed in the time span of one month. 4 RESULTS 4.1 Performance and usability evaluation Evaluation results in terms of completion time, rotation and zoom error rates are shown in Tables 1-3. Average values, standard deviations, min and max values calculated over all tasks and users are given for each device, rounded to one decimal place. A general linear model of repeated measures has been used to identify the possible statistically significant differences (p < 0.05) between input devices using Analysis of variance (ANOVA) in terms of the defined dependent variables. The results show that the Leap Motion controller yielded significantly worse completion times than both the regular and the 3D mouse (p < 0.0001). The Leap Motion controller also showed significantly higher rotation error rates than the 3D mouse (p < 0.0005). On the other hand, the regular mouse had significantly lower zoom error 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 101 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations Table 1: Task completition times aggregated across all tasks for each device separately. Lower values (in bold) indicate better performance. Input device Average time (s) Standard deviation (s) Fastest time (s) Longest time (s) Mouse 36.6 27.1 5.0 196.0 3D Mouse 35.4 28.5 4.0 196.0 Leap Motion 64.5 46.6 11.0 285.0 Table 2: Rotation error rate in arc degrees (°) aggregated across all tasks for each device separately. Lower values (in bold) indicate better performance. Input device Average err. (°) Standard deviation (°) Lowest err. (°) Highest err. (°) Mouse 17.1 37.9 6.2 210.0 3D Mouse 10.6 23.3 0.1 191.0 Leap Motion 21.9 46.7 0.3 256.0 Table 3: Zoom error rate aggregated across all tasks for each device separately. Lower values (in bold) indicate better performance. Input device Average err. (%) Standard deviation (%) Lowest err. (%) Highest err. (%) Mouse 34.1 80.2 0.0 800.0 3D Mouse 52.9 60.7 0.0 396.0 Leap Motion 58.9 71.7 0.0 600.0 rates than the 3D mouse (p < 0.005) and the Leap Motion Controller (p < 0.0001). Correlational tests showed that the participants' previous experience with various input devices and 3D manipulation did not significantly influence their performance in the 3D docking tasks. Results of the SUS questionnaire are presented in Table 4, where the average SUS value for each user for each individual input device is calculated according to the methodology presented in (Brooke, 1996; Bangor et al., 2009; Lewis and Sauro, 2009; Brooke, 2013). Minimum and maximum achieved SUS scores are also shown for each input device. The descriptive SUS interpretation is added according to the (Bangor et al., 2009; Brooke, 2013). 4.2 User observation and interviews While observing the participants, we noticed they had problems while trying to achieve rotational as well as zoom precision with the Leap Motion Controller. Our follow up questions showed that the main reason for this was the lack of feedback when participants waved their hands above the device, which caused some confusion. They had problems remembering the correct gestures for individual actions (how to move the hands to rotate or zoom) and remembering to close the palm for stopping interaction and to open the palm for resuming it, thus unintentionally triggering interaction. They also reported some frustrations when trying to make very precise movements. On the other hand, some of the users felt that such touchless interaction presents a very natural way of interaction and said that the actions were intuitive. The majority of the participants were very satisfied with the 3D mouse, which we attribute to the fact that movements of the 3D mouse directly reflected in the movements of the objects. Therefore, users did not need to remember certain gestures and motions so they could concentrate more on completing the tasks and less on how to handle the device itself. Table 4: Results of the SUS scores questionnaires showing input device performance in terms of usability. Higher score (in bold) means better performance. Input device Average score Standard deviation Minimum score Maximum score SIS score interpretation Mouse 72.4 18.4 45 97.5 Good/C 3D Mouse 88.7 11.4 50 100 Excellent/B Leap Motion 56.5 19.0 20 95 OK 102 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations From the interviews, we also extracted that most of the users performed the tasks as fast as possible and paid less attention to precise positioning. None of the users had problems with fatigue or distractions. There were some minor problems with the experimental setup; in these cases, we disposed the invalid data and repeated the erroneous part of the experiment. 5 DISCUSSION 5.1 Completion time Hypothesis H1 predicted that the Leap Motion Controller will be the slowest device, while the mouse and the 3D mouse will be closer together in terms of time required to complete the 3D docking tasks. Table 1 shows that the average time for completing each task was 45 seconds. Completing tasks with a mouse took 37 seconds on average, with 3D mouse 35 seconds, and with the Leap Motion Controller 65 seconds. The participants were able to complete the tasks with the mostly unfamiliar 3D mouse just as fast as with the familiar mouse, which makes the 3D mouse a good alternative to mouse in terms of speed. On the other hand, statistical tests confirmed that the Leap Motion Controller required significantly more time than both other alternatives. These results confirm hypothesis H1 and are all in line with the results of other studies presented in Section 2. 5.2 Rotation error rate Hypothesis H2 stated that there will be no significant differences between the tested input devices. Results (Table 2) showed that the average rotation error rate for all input devices was 16.5°. The average rotation error rate achieved with the regular mouse was 17.1°, with the 3D mouse 10.6° and with the Leap Motion Controller 21.9°. There was no significant difference between the regular mouse and other two input devices, but there was a significant difference between the 3D mouse and the Leap Motion Controller, so we cannot confirm hypothesis H2. The results also show that the users were able to rotate most accurately with the 3D mouse. By combining the completion time results, our results show that the 3D mouse is a good choice when rotational precision and speed are needed. Again, the Leap Motion performed the worst. 5.3 Zoom error rate The hypothesis H3 also stated there will be no significant differences between the tested input devices in terms of zoom error rate. Results (Table 3) show that the average zoom error rate for all input devices was 48.6%. The average zoom error rate achieved with the regular mouse was 34.1%, with the 3D mouse 52.9% and with the Leap Motion Controller 58.9%. From the results, we can conclude that zooming is best performed with a regular mouse, where the average zoom error is the lowest. However, standard deviation shows that users made more consistent mistakes with the 3D mouse than they did with a regular one. The difference can be attributed to the fact that zooming with a regular mouse is performed in discrete steps due to the functioning of the mouse wheel, which makes it easier to select an appropriate zoom level. The 3D mouse has a continuous zoom, which makes it harder to judge the small differences when adjusting for the appropriate zoom level. There is no significant difference between the 3D mouse and the Leap Motion Controller, but there is a significant difference between the mouse and both other devices, so hypothesis H3 could also not be confirmed. 5.4 Usability The user study also aimed to evaluate the usability aspect of the tested input and hypothesis H4 stated all three input devices will be suitable for the tested application with a SUS score equal or better than »OK«. Results (Table 4) show that the average SUS score for all input devices was 72.5. The average SUS score achieved with the regular mouse was 72.4, with the 3D mouse 88.7 and with the Leap Motion Controller 56.5. The participants really liked the implementation of the 3D mouse and most of them (21) would gladly recommend this device to other people. After matching the results to an adjective rating scale, the regular mouse modality scored »Good/C«, the 3D mouse »Excellent/B«, and the Leap Motion Controller »OK«. From these results, we can conclude that the usability of a regular mouse and 3D mouse is acceptable, whereas the Leap Motion Controller has a low marginal score, but still scores an »OK« on the adjective rating scale, so we can confirm hypothesis H4, as all three devices were evaluated as suitable. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 103 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations 5.5 Overall impression and user preference The hypothesis H5 predicted that the participants will tend to favor the Leap Motion Controller due to its novelty factor. Our results actually show that the participants were more impressed by the 3D mouse, which was also an unfamiliar device for most participants, but was easier to handle. One of the reasons why the Leap Motion performed so poorly might be in the implementation of the gestures used to manipulate the test object in 3D space. The interaction with the test object was started by opening the palm of the hand above the sensor. Hand movements to the left and right rotated the object about the vertical axis, and movement up and down rotated the object about the horizontal axis. Moving the hand closer to the screen or away from the screen resulted in zooming action. One could also tilt the palm about the horizontal axis that pierced the screen which resulted in the rotation about this axis. When considering all of the presented factors, the 3D mouse is the most appropriate input device, and the best choice in terms of rotation precision and usability, and equivalent to the regular mouse in terms of completion time. The regular mouse also provides solid performance in all aspects. However, the Leap Motion Controller has not yet reached its full potential. On the one hand, it provides a natural an intuitive interaction, on the other hand the interaction is slower compared to the other two input devices and also has higher error rates and lower usability. 6 CONCLUSIONS AND FUTURE WORK We presented a study that evaluated three different input devices for 3D docking tasks in a modified 3D medical visualization application that requires high precision. The devices tested were: regular mouse, a 3D mouse, and the gesture-based Leap Motion Controller. We compared the performance (completion time, rotation and zoom error rates) and usability of all three input devices on 7 different 3D docking tasks in randomized order with a total of 29 participants. Results show that the 3D mouse is the most appropriate input device in terms of rotation precision, equivalent to regular mouse in terms of completion time, and has also received favorable subjective assessments. The 3D mouse also achieved the best usability score. Considering the poor performance of the Leap Motion Controller, we conclude that this novel input device is not ready yet to be used in everyday environments despite its suitability in sterile environments such as hospital operation rooms. However, user feedback still leads us to believe that it is a promising natural touchless interface once its precision and interaction model is improved. Our results show that even though the gesture-based interaction felt natural to the participants, the gestures still had to be learned and are in fact not as closely matched to the 3D interaction on desktop computers as those of a 3D mouse. The comments and opinions we gathered through the 3D docking tasks performed with the Leap Motion Controller will be used in a new release of the NeckVeins application. We have also implemented a new gesture setup for interacting with the Leap Motion Controller, which we plan to evaluate in our future work. Overall, our study finds the 3D mouse as the most promising input device for 3D visualizations among those that are readily available on the market and are easy to add to existing 2D desktop setups. We therefore recommend further research to include this device in real-world situations to fully explore its potential when precision and ease of use are needed in manipulating 3D visualizations. Because our study included a diverse group of participants, we believe the results of our work can also apply to other types of precise 3D visualizations that are used by non-expert users, especially when long training is not an option. As part of future work, we plan to further explore similar scenarios and add support for new types of natural input interfaces, such as touch and voice input. 7 ACKNOWLEDGEMENTS The authors would like to thank all the participants in the experiment for volunteering and taking their time helping in our study. We would especially like to thank the users of the pilot study that gave us many good suggestions on how to improve the experiment as well as how to adapt the testing application. 8 REFERENCES [1] Bade, R., Ritter, F., and Preim, B. (2005). Usability Comparison of Mouse-Based Interaction Techniques for Predictable 3D Rotation. Smart Graphics, 3638, pages 138-150. [2] Balakrishnan, R., Baudel, T., Kurtenbach, G., and Fitzmaurice, G. (1997). The Rockin'Mouse: Integral 3D Manipulation on a Plane. In Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems, pages 311-318. ACM. 104 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations [3] Bangor, A., Kortum, P., and Miller, J. (2009). Determining What Individual SUS Scores Mean: Adding an Adjective Rating Scale. Journal of Usability Studies, 4:114-123. [4] Besançon, L., Issartel, P., Ammi, M., and Isenberg, T. (2016). Usability Comparison of Mouse, Touch and Tangible Inputs for 3D Data Manipulation. CoRR. [5] Bhuiyan, M. and Picking, R. (2011). A Gesture Controlled User Interface for Inclusive Design and Evaluative Study of its Usability. Journal of Software Engineering and Applications, pages 513-521. [6] Bohak, C., Žagar, S., Sodja, A., Škrlj, P., Mitrovic, U., Pernuš, F., and Marolt, M. (2013). Neck Veins: an Interactive 3D Visualization of Head Veins. In Proceedings of the 4th International Conference World Usability Day Slovenia 2013, Ljubljana, Slovenia, 25th November 2013, pages 64-66. [7] Bowman, D. A., Kruijff, E., LaViola, J. J., and Poupyrev, I. (2001). An Introduction to 3-D User Interface Design. Presence: Teleoperators and Virtual Environments, 10(1), pages 96-108. [8] Brooke, J. (1996). SUS - a Quick and Dirty Usability Scale. Usability Evaluation in Industry, pages 189-194. [9] Brooke, J. (2013). SUS: A Retrospective. Journal of Usability Studies, 8(2):29-40. [10] Coelho, J. C. and Verbeek, F. J. (2014). Pointing Task Evaluation of Leap Motion Controller in 3D Virtual Environment. In Creating the Difference: Proceedings of the Chi Sparks 2014 Conference, pages 78-85. [11] Ebert, L. C., Hatch, G., Ampanozi, G., Thali, M. J., and Ross, S. (2012). You Can't Touch This Touch-Free Navigation Through Radiological Images. Surgical Innovation, pages 301-307. [12] Gratzel, C., Fong, T., Grange, S., and Baur, C. (2004). A Non-Contact Mouse for Surgeon-Computer Interaction. Technology and health care: Official Journal of the European Society for Engineering and Medicine, 12:245-257. [13] Hinckley, K., Tullio, J., Pausch, R., Proffitt, D., and Kassell, N. (1997). Usability Analysis of 3D Rotation Techniques. In Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology, pages 1-10. ACM. [14] Jankowski, J. and Hachet, M. (2015). Advances in Interaction with 3D Environments. Computer Graphics Forum, 34(1):152-190. [15] Lewis, J. R. and Sauro, J. (2009). The Factor Structure of the System Usability Scale. In Proceedings of the 1st International Conference on Human Centered Design: Held As Part of HCI International 2009, HCD 09, pages 94-103, Berlin, Heidelberg. Springer-Verlag. [16] Nielsen, J. (2012). Usability 101: Introduction to Usability. https://www.nngroup.com/articles/usability-101 -introduction-to-usability/. Accessed: 2018-08-22. [17] Ortega, F. R., Abyarjoo, F., Barreto, A., Rishe, N., and Adjou-adi, M. (2016). The Light Pen and the Computer Mouse, chapter 1.2.4, pages 10-13. A K Peters/CRC Press. [18] Perelman, G., Serrano, M., Raynal, M., Picard, C., Derras, M., and Dubois, E. (2015). The Roly-Poly Mouse: Designing a Rolling Input Device Unifying 2D and 3D Interaction. In Proceedings of the ACM CHI'15 Conference on Human Factors in Computing Systems, volume 1, pages 327-336. ACM. [19] Pike, W. a., Stasko, J., Chang, R., and O'Connell, T. A. (2009). The Science of Interaction. Information Visualization, 8(4), pages 263-274. [20] Rosa, G. M. and Elizondo, M. L. (2014). Use of a Gesture User Interface as a Touchless Image Navigation System in Dental Surgery: Case Series Report. Imaging Science in Dentistry, 44, pages 155-160. [21] Ryu, Y., Koh, D. D. H., and Um, D. (2011). Usability Evaluation of Touchless Mouse Based on Infrared Proximity Sensing. Journal of Usability Studies, 7, pages 31-39. [22] Teather, R. and Stuerzlinger, W. (2010). Target Pointing in 3D User Interfaces. In Graphics Interface (GI 2010), pages 20-21. [23] van Dam, A. (1997). Post-WIMP User Interfaces. Communications ACM, 40(2), pages 63-67. [24] Yu, L., Svetachov, P., Isenberg, P., Everts, M. H., and Isenberg, T. (2010). FI3D: Direct-Touch Interaction for the Exploration of 3D Scientific Visualization Spaces. IEEE Transactions on Visualization and Computer Graphics, 16, pages 1613-1622. ■ Ciril Bohak is a Teaching Assistant at the Faculty of Computer and Information Science, University of Ljubljana. His research includes Human-Computer Interaction, Computer Graphics, Music Information Retrieval, Gamification, E- Learning and Game Technology. Currently he is teaching courses Computer Graphics, Game Technology and Computer Aided Design. He is one of the founding members of Slovenian HCI community. ■ Jože Guna is an Assistant Professor at the Faculty of Electrical Engineering, University of Ljubljana. His area of research focuses on Internet technologies, multimedia technologies, IPTV systems and VR/AR/M technologies with special emphasis on user-centered design, user interaction modalities and designing the user experience, including gamification and flow aspects. He is a PI of several projects. He is an expert in Internet, ICT and IPTV technologies and holds several industrial certificates from CISCO, Comptia and Apple, including trainer licenses from Cisco and Apple. He is a senior member of the IEEE organization. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 105 Ciril Bohak, Jože Guna, Peter ŠkrLj, Alja Isakovič, Matija Marolt: A usability comparison of input devices for precise and intuitive interaction with 3D visualizations ■ Peter Škrlj graduated at University of Ljubljana, Faculty of Computer and Information Science in 2014. His bachelor thesis focused on evaluating usability and ease of use of different navigation devices while manipulating a 3D medical image. His fields of interest vary from computer graphics, game design, internet technologies, mobile device development and computer vision. He is currently enrolled in the master's program at University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies. ■ Alja Isakovic is currently UX advisor at Cofound.it One. As a member of LGM (Laboratory for Computer Graphics and Multimedia) and researcher in the field of human-computer interaction, she is currently exploring new data-gathering user interfaces and ways for monitoring user interaction in post-PC web browsers. She previously spent three years at CubeSensors, an loT hardware startup, at which she led user experience design and research. ■ Matija Marolt is an assistant professor with Faculty of Computer and Information Science, University of Ljubljana, where he has been working since 1995. He is head of Laboratory for Computer Graphics and Multimedia, where his research interests include music information retrieval, specifically semantic description and understanding of audio signals, retrieval and organization in music archives, and human-computer interaction. 106 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI ZNANSTVENI PRISPEVKI B Community detection in Slovene public spending Skupnosti v slovenskem javnem naročanju Vitjan Zavrtanik, Lovro Šubelj University of Ljubljana, Faculty of Computer and Information Science, Večna pot 113, 1000 Ljubljana vitjan.zavrtanik@gmail.com; lovro.subelj@fri.uni-lj.si Abstract Government public spending is a highly complicated system with many endpoints, as government funding has to be distributed to a large number of institutions that purchase goods and services using public funds from a large number of public and private organizations. Even though there are mechanisms in place which control public spending by either entrusting control to a public institution or by prescribing legal procedures that must be observed when purchasing services, these procedures are sometimes unreliable or enable exploitation. Procedures often comprise public tenders which can be exploited by bidding private firms or public servants. We hypothesise that there are patterns in such behaviour that could perhaps be identified via community detection in the public spending transaction network by examining publicly available transaction data on public funds. Keywords: public spending, community detection, network analysis. Izvleček Sistem porabe javnega denarja je kompliciran predvsem zaradi potrebe po primernem razporejanju med številne državne institucije, ki sredstva porabljajo za blago in storitve potrebne za njihovo delovanje. Zaradi ogromnega števila transakcij je sistem težko nadzorovati in čeprav obstajajo mehanizmi za nadzorovanje porabe kot so javni razpisi, obstaja možnost manipulacije postopka izvajanja razpisa s strani podjetij v privatni lasti, ki se na razpis prijavljajo, ali pa s strani javnih uslužbencev, ki razpis prijavijo. Naša hipoteza je, da v takem obnašanju obstajajo vzorci, ki bi jih lahko razbrali z detekcijo skupnosti v omrežju transakcij javnih sredstev. Ključne besede: poraba javnih sredstev, detekcija skupnosti, analiza omrežij 1. INTRODUCTION Allocating and distributing funds is a complicated problem. A great deal of government effort goes directly into the deciding how and when to spend public funds, a majority of which goes into the essential systems such as healthcare, education and pensions which are comprised of many public institutions and are also the primary source of income for a significant percentage of private companies. Due to the vast amount of resources such public institutions utilise, there are quite a few regulations that must be followed, some of which are defined in (Zakon o javnem 2018 - številka 3 - letnik XXVI narocanju (ZJN-3), 2015). One of the procedures for procuring required services and goods from companies is the public tender which enables institutions to publicly announce that they require a certain service and the companies that perform that service are able to present their offers for the service. Often the public institution is obligated to purchase the service from the lowest bidder. Other times stricter criteria are involved in choosing the winning bid on a public contract, which is often the cause of conflict as the institution requiring the service is accused of corruption by overfitting the selection process to a certain bidder. uporabna INFORMATIKA 107 Vitjan Zavrtanik, Lovro Subelj: Community detection in Slovene public spending One example of such controversial activity is the recent construction of the railroad project showcase model in which the institution providing the contract first picked the more expensive bidder based on a certain criteria and the selected company later hired a less expensive bidder that was not selected to perform a portion of the service it was contracted to do (MMC RTV SLO, 2018). While the idea of public tenders seems good on paper, it has flaws in its enforcement and regulations. It has often been criticized for the possibility of fine tuning the tender documentation to better suit a specific bidder. There is also a possibility of offer price fixing by the participating bidders. If the managers of the bidding companies knew each other, they could easily change the offer price for a certain tender which could raise the profits. Such price fixing is illegal. We could hypothesise that there is a higher chance that price fixing occurs if the people in these companies know each other and perhaps the companies even often work together. There is unfortunately no publicly available data that shows direct business cooperation between privately owned companies as they are not obligated to report such data. The transaction data between public or between public and private institutions are publicly available and searchable on the Erar tool (Commission for the Prevention of Corruption, 2018) maintained by the Commission for the Prevention of Corruption. The transaction data is available for download in the csv file format for each fiscal year separately. This data can be parsed into a network representation where nodes are public and private institutions and the links between them are the transactions or the sums of transactions between them. This gives us a network which depicts the flow of funds from public institutions to private ones. While this could be used to analyse a variety of the system properties. 2. RELATED WORK In (Kolar & Kolar, 2017) the data from Erar (Commission for the Prevention of Corruption, 2018) was used to rank the importance of institutions in the network and was used to simulate the robustness of the network to node and edge removals. In (Kogov-sek, Sovdat, & Povsic, 2013) similar data was used, however they decided to connect owners and repre- sentatives to companies based on their affiliation and attempted to discover communities. In (Lozano, Duch, & Arenas, 2006) the authors use a method based on modularity measures (Girvan, 2002) to discover communities in a large social dataset of European projects. There are many community detection algorithms available ( (Rosvall & Bergstrom, 2008), (Blondel, 2008), (Ahn, Bagrow, & Lehmann, 2010)) however for a network as large as ours algorithms with the computational complexity of O(n2), where n is the number of nodes in the network are not feasible for executing on a personal computer since the execution time needed for the method to finish is substantial. In (Subelj, Jan, & Waltman, 2016) the authors evaluate a variety of clustering methods on citation networks. 3. DATA AND METHODS We gather all of the used data from the Erar tool (Commission for the Prevention of Corruption, 2018). The transaction data is available in csv format and is available on a yearly basis from the year 2003 onward. We use the transaction dataset for the year 2017 to reduce the amount of data needed to process, however this is still a list of approximately 23 million transactions between about 88000 private and public institutions. We are however not as interested in the network we can generate from this data directly but in the network that we can construct with the addition of representation and ownership data. Ownership and representation data is available through the Erar API (Commission for the Prevention of Corruption, 2018), which we must query for every institution. We can gather the data on present and past ownership and representation. We hypothesize that the cooperation between companies and institutions is not based only on the institutions themselves but on the people that represent or own these companies. Since we have the ownership and representation data of the companies we can instead construct a network of people which could give us some insight in the cooperation between private companies for which the data is not publicly available as it is likely that the people who are or were once co-owners or representatives of companies know each other. Because of this we assume that there is a certain community structure that could be extracted. In (Kogovsek, Sovdat, & Povsic, 2013) community detection on a similarly constructed network has 108 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending been done using modularity maximization methods that have trouble detecting smaller networks due to the resolution limit ( (Barabasi & Posfai, 2016), (Fortunato & Barthelemy, 2007)). This may be important for this specific problem as the communities that we are looking for could be much smaller, especially if we want to extract information of the possibility of collusion on public tenders. Appropriate algorithms for a network of this size are Infomap (Rosvall & Bergstrom, 2008) and Lou-vain (Blondel, 2008) methods as they excel in speed with the computational complexity of O(n log(n)), where n is the number of nodes in the network. The Louvain method is, however, also a modularity maximization algorithm and is therefore also affected by the resolution limit. We also wanted to test the performance of a further subdividing the induced graph of the larger acquired communities using perhaps less scalable community detection methods such as (Ahn, Bagrow, & Lehmann, 2010). 3.1 Data preparation In order to construct the network, the extracted data from Erar (Commission for the Prevention of Corruption, 2018) had to be augmented with the Register of budget users downloaded from the Ministry of finance database (Uprava Republike Slovenije za javna plačila, 2018). This additional data was required as Erar's transaction data does not contain the name of the institution who issued the transactions and instead only lists the bank account from which the funds were taken. We had to extract a list of bank accounts from all the public and private institutions from Erar and match the account to the transaction data in order to get the names of the institutions transferring the funds. After constructing the list of institutions, we had to again query Erar in order to get the list of representatives and owners of the discovered business entities. We constructed the network so that the edges are present between two people either if they work or had previously worked in the same institution, or if the institutions for which they worked are connected by a transaction. This gives us the possibility of using two types of edges in the graph which could show whether two people are affiliated only by working for the same company or due to some business activity between the two companies. The nodes could also be divided into people representing public insti- 2018 - številka 3 - letnik XXVI tutions and people owning or representing private companies. It is worth mentioning that there are quite a few people who worked in both the public and private sector. 3.2 Person to person network The constructed network consists of 157417 nodes representing the individuals working in public and private institutions. The network contains 1683451 edges. A large portion of the edges are due to the way we connected the people in the graph. We assumed that two people know each other and could collaborate if they both worked as representatives of the same firm. As a result of this, individual companies are represented as cliques. Another assumption that we made was that if there was some business done between two companies, the representatives of these companies know each other. This assumption may be inaccurate when dealing with large institutions such as major banks, where the number of representatives and number of transactions is very high, which obviously makes the representatives of the bank highly connected due to the number of entities the bank does business with. Of course we cannot assume that a bank representative is aware of every single transaction, therefore the assumption is violated. The disproportionately large number of connections for large institution representatives makes it difficult to accurately analyse the actual connections between the representative and other individuals. The degree distribution of the extracted network can be seen in Figure 1, where we can see that the distribution is roughly scale free. The average degree is = 21.38 and the maximum degree kmax= 5775 which belongs to one of the bank representatives described previously. 4. RESULTS We used the community detection algorithms Infomap (Rosvall & Bergstrom, 2008), Louvain (Blon-del, 2008), Label Propagation (Cordasco & Gargano, 2010) and METIS (Karypis & Kumar, 1998) to extract community structure data from the constructed network. Some results can be found in Table 1 where we can see that Louvain, Infomap and Label Propagation algorithms detect a large number of communities and that the average size of these communities is fairly low. This can be explained by examining our uporabna INFORMATIKA 109 Vitjan Zavrtanik, Lovro Subelj: Community detection in Slovene public spending 10° Iff1 10 £ ID"3 10'* 10 s id" Degree distribution |c Figure 1: Node degree distribution using log binning on a log-log scale. data where we can see that there are many nodes that are connected only to a very low number of other nodes which could cause the algorithms to exclude them from other communities. These low degree nodes often represent individual contractors that appear in the data because they probably did some work for the government in the fiscal year 2017, but are not connected to any other institution. The METIS method is a k-way graph partitioning algorithm and is dependent on the partition number parameter K as it will partition the graph more or less uniformly into K clusters. Contrary to other methods it's resolution is arbitrarily high and can be used to partition the graph into many small clusters. This seems like a favourable quality for our application as we want to observe small clusters of people and their connections in the network. In practice however the algorithm depends so much on K that the resulting clusters make no sense if K is set too high or too low. In (Subelj, Jan, & Waltman, 2016) good results were achieved by using METIS in conjunction with other community detection algorithms. We combined the Louvain and METIS methods so that the communities are first detected with Louvain and are then further subdivided using METIS as some of the communities detected by Lo-uvain are very large. In Table 1 we can see that the combination of methods does indeed subdivide larger communities detected by Louvain however the quality of these subdivisions again depends on K and on the communities that are being subdivided as there are some large communities that cannot be partitioned in a sensible way without losing information about the network structure. In Table 1 we can also see that the sizes of maximum communities are quite high. This is not unexpected since there are individual nodes with a very high degree as described in Subsection 3.2 and it is also frequently the case that these nodes are connected to each other forming a strong community structure. The distribution of the community size is also quite different depending on the method that is used as we can see in Figure 3, Figure 4, Figure 5 and Figure 6. We can see that the Louvain+METIS method results in very small clusters however this depends on the choice of the K parameter. The other methods typically results in a much higher probability of large communities. 110 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending Table 1: Number of communities detected, average, maximum and minimum size of the detected communities for each of the utilized community detection methods. Method K community Ka»g K max Kmin Louvain 43692 3.6 23832 1 Infomap 47251 3.33 3672 1 Label prop. 43819 3.59 22298 1 METIS 10000 15.74 17 11 Louvain+METIS 47223 3.32 45 1 Table 2: Number of communities detected (Kcommunity), average (Kavg), maximum (Kmax) and minimum (Kmin) size of the detected communities for METIS executions with different partition number parameters (K). K K community Ka»g K max Kmin 100 100 1574.3 1620 1459 1000 1000 157.44 162 141 10000 10000 15.74 17 11 20000 19996 7.87 11 4.1 Evaluation Due to no known community structure of the data, we have no data to compare it with. This makes evaluation of the results difficult. We can of course manually look at the results and interpret the quality of the discovered communities however this is time consuming and not quantifiable. Figure 2: Personal community with a single detected community. Nevertheless, this approach seems to be useful if we visualize a discovered community that contains a certain individual. Many times it finds an informative representation of the business network of a certain person. It shows us which people that person is in business with and with which people that person has interacted by working in the same company. As 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 111 Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending Figure 3: Louvain method community size distribution. 10° 10" 10" 10" 10" Community size distribution • • • • * • • • • • • • _ • • ••• • • ..... _t........1_t_k.......1_t_t__ ........*—. . * ... 10" 10" 10" 101 10' 10J 10" Figure 4: Label propagation method community size distribution. 112 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending mentioned in Subsection 3.2, there is limited usability of this approach for individuals that turn out to be hubs in our network, as the data is rarely accurate since we assume that if business is being conducted between two entities, the representatives must know each other. We found that a visualization of a person's community is frequently sensible if we visualize the detected community of a certain node and the neighbours of all the members of the detected community. Visualizing neighbours gives us additional information which is frequently needed since the detected community is regularly composed of people within a single company. The neighbour approach sometimes fails to work for visualizing the surrounding community as the companies are often well separated from the rest of the network. An example of this can be seen in Figure 2. A significant problem that we are running into and currently have no way of fixing is our inability to distinguish between individuals with the same name. We assume that the majority of individuals have a name that is unique enough that there are no other owners or representatives of companies with the same name however we can never be sure. This of course is not always the case which is why we have nodes in our data that are vastly more connected than they should be due to the fact that it represents multiple people, for example the node that represents Janez Novak is connected to several hundred nodes only by affiliation with 17 different entities which of course were not founded by a single Janez Novak. The visualization for this graph is therefore not informative at all and the subgraph is also composed of several large communities. There are currently no possible ways of mending this issue as the data required, such as personal identification numbers, are not publicly available. The visualization of the communities is quite difficult since we want to display the names of the individuals as well as the companies with which they are affiliated. In the event of a larger community the visualization often gets filled with text and would require an alternative solution to visualizing this data. An example of a poorly readable visualization can be seen in Figure 7. iou 10" 10"' io- 10" Community size distribution • .....' ' 'T ' »I»I»PI| * i . i 1 1 1 1 ' ....... • • • • • • • • • • • • • • • • • ....... • • • ......—L - ....... 1 - ... ■ ... 1 . . ...... 10" 10" 10" 101 10 10 10 Figure 5: Infomap method community size distribution. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 113 Vitjan Zavrtanik, Lovro Subelj: Community detection in Slovene public spending Figure 6: Louvain + METIS method community size distribution. 4.2 Visualization As we can see in Figure 7, the visualization of the communities is lacking in clarity due to the overlapping text and uninformative node colours. We significantly reduced the font size of the information displayed for each node and reduced the amount of information that is displayed by text. In Figure 7 we see that the both the entity name and the institution it is affiliated with are written over the node, in cer- tain individuals the number of affiliated institutions is very high resulting in a block of text that is hard to read. We decided that it is better to remove most of the affiliation information from the visualization and instead use node colours to show which people belong to the same institution. We previously used colour coding to display which discovered community a certain node belongs to. This information is lost from FtAPU d V logahac Figure 7: Multiple detected communities. The figure showcases the problematic visualization when depicting larger networks. 114 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending the visualization however we feel that the information is not as relevant to the observer as a single visualization contains all the nodes of a single community and their neighbours and is therefore in part still contained within the subgraph. The colour coded information is of course shown within the legend adjacent to the network visualization. The edges in the graph can signal that the nodes are connected by affiliation with the same company, a transaction between two institutions or by both. We coloured the different types of links so that the nature of the connection between two nodes is more apparent. The community displayed in Figure 2 is better visualized in Figure 8 where only the names of the individuals are displayed as text and the company names are listed in the legend. 4.3 Connection type The edges in our network can be a result of two factors. An edge can either be present due to a direct collaboration between two entities signalled by a transaction between them, or due to two individuals representing the same organization. This gives us 3 distinct edge types, since edges can be present due to transaction, affiliation or both. We were especially interested in the latter as an edge of this type would mean that the individuals presented by the nodes are were at one time affiliated with the same institution and that there is a possibility that they are now handling transactions of public funds. There are very few cases where people are involved with both public and private institutions and are doing business with the public institution that employed them. Edges of this type mostly appear in transactions between public institutions. In the cases where one of the connected nodes is a representative of a private company, business is mostly conducted with a representative of the local community of the area where the company operates. In the majority of such cases, the representative of the public institution was previously at the same private company as the service provider. These sort of transactions could be legitimate since local communities are usually small and it is possible that there are no other companies in the area that offer the same kind of services. The fact that these people are connected by previous employment in the private sector should still be taken into consideration when reviewing these transactions. Our network has only 64 such edges. One of the possible reasons why the occurrence of these edges is so low is because we only use the transaction data XIANXING d o.o ;"X") HUA LI. d.O.O. jitsl FAN d.o.o. Figure 8: Personal community with a single detected community with the updated visualization. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 115 Vitjan Zavrtanik, Lovro Subelj: Community detection in Slovene public spending for 2017. If we were to add the data from the previous years, the number of these edges would probably be higher. We also lack data on which we could build additional connections between individuals. In order to build an accurate representation, we would require data that would enable us to link people on a social level as it would be foolish to assume that such transactions only happen between individuals that were previously in business with each other. An example of the required data would be social information such as family members or friends. We also lack transactional information between private entities which would, without a doubt, be very informative, however such information is not of public nature. The affiliation and transaction edges are much more common. In our network there are 1495876 affiliation connections and 255896 transactional connections. The large number of affiliation links is not surprising since each company is represented as a clique and therefore has the maximal number of edges between members of the same company. 5. DISCUSSION We have gathered the transaction, ownership and representation data from Erar's (Commission for the Prevention of Corruption, 2018) database and converted it into a network of individuals active in the Slovene public spending system. We tested several community detection approaches with the goal of discovering small densely connected communities of people connected by either affiliation through employment at the same company or by a public transaction. The examined community detection methods return vastly different communities. Methods such as Infomap (Rosvall & Bergstrom, 2008), Louva-in (Blondel, 2008) and Label Propagation (Cordasco & Gargano, 2010) can return very large communities that can be subdivided using algorithms such as METIS (Karypis & Kumar, 1998), however the resulting subdivision is often poor as further division is sometimes not appropriate as some individuals simply do business with many others which is why their community is proportionally larger. It is difficult to evaluate how well each community detection algorithm performs on the network as we do not know what the actual communities are. We can check results for different individuals and see whether the returned community makes sense, but we cannot confidently state that a certain algorithm outperforms the others. We are still facing issues with proper visualization as we have a lot of data that needs to be displayed in text such as names of individuals and companies and there is simply no space for a proper visualization when displaying a graph with more than 50 nodes or even less if the nodes are densely connected which they often are. Our hope for this work was to discover significant smaller, tightly connected communities of individuals working in the entrepreneurial space of Slovenia, that are connected to public institutions. We were interested in seeing whether such communities exist and how well they are connected to individual public establishments. We also wanted to examine whether such communities could potentially collude to influence the results of public tenders offered by a specific organisation. We wanted to see whether there are representatives of public establishments that are also part of these communities. We discovered that the network is indeed mostly constructed out of small connected communities however these communities are often large enough to cause issues with our visualization. There are also a few individuals who are very well connected and are therefore a part of larger communities that are very hard to properly visualize. It is very hard to conclude anything about possible collusion between two representatives of public and private institutions since we lack the information to further connect business owners to public representatives. The only way to connect them in the context of our data is if both parties were once members of the same institutions and are now responsible for transactions between certain private and public institutions. As mentioned in Subsection 4.3, such connections are very rare and we would require data that is not of public nature to accurately identify representatives where the risk of collusion is higher. An analysis of this sort could be much better if we had access to additional data and not just the transactional data of public companies. A government institution such as the Commission for the Prevention of Corruption would be much better suited to perform such research as more data is more readily available to them. 116 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Vitjan Zavrtanik, Lovro Šubelj: Community detection in Slovene public spending 6. REFERENCES [1] Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466(7307), 761. [2] Barabasi, A.-L., & Posfai, M. (2016). Network Science. Cambridge University Press. Pridobljeno iz http://barabasi.com/ networksciencebook/ [3] Blondel, V. D.-L. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment. Pridobljeno iz https://arxiv.org/abs/0803.0476 [4] Commission for the Prevention of Corruption. (2018). Erar API. Pridobljeno iz https://erar.si/doc/: https://erar.si/doc/ [5] Commission for the Prevention of Corruption. (2018). Erar, aplikacija za prikaz porabe javnega denarja v Republiki Sloveniji. Pridobljeno iz https://erar.si/ [6] Cordasco, G., & Gargano, L. (2010). Community detection via semi-synchronous label propagation algorithms. IEEE International Workshop on Business Applications of Social Network Analysis (BASNA), 1-8. [7] Fortunato, S., & Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1), 36-41. [8] Girvan, M. a. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12), 7821-7826. [9] Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1), 359-392. [10] Kogovšek, R., Sovdat, B., & Povšič, R. (2013). Analysis of Slovene Company Ownership Network. AS113/14 project. [11] Kolar, A., & Kolar, L. (2017). Resilience Analysis of the Slovene Economy. AS117/18 project. [12] Lozano, S., Duch, J., & Arenas, A. (2006). Community detection in a large social dataset of european projects. Pridobljeno iz https://archive.siam.org/meetings/sdm06/workproceed/ Link%20Analysis/17FP6-SIAM.pdf [13] MMC RTV SLO. (2018). Je za izbiro dražje makete kriv Excel ali dogovarjanje med ponudniki? Pridobljeno iz https://www. rtvslo.si/gospodarstvo/je-za-izbiro-drazje-makete-kriv--excel-ali-dogovarjanje-med-ponudniki/448670 [14] Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118— 1123. [15] Šubelj, L., Jan, V. E., & Waltman, L. (2016). Clustering scientific publications based on citation relations: A systematic comparison of different methods. PloS one, 11(4), 0154404. Pridobljeno iz https://journals.plos.org/plosone/ article?id=10.1371/journal.pone.0154404 [16] Uprava Republike Slovenije za javna plačila. (2018). Seznami registra proračunskih uporabnikov. Pridobljeno iz https:// www.ujp.gov.si/dokumenti/dokument.asp?id=127 [17] Zakon o javnem narocanju (ZJN-3). (2015). Ljubljana: Uradni list RS, num. 91, pg. 10201. Pridobljeno iz https://www.uradni-list.si/ glasilo-uradni-list-rs/vsebina/2015-01-3570?sop=2015-01-3570 ■ Vitjan Zavrtanik končuje magistrski program računalništva in infromatike na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Zanimajo ga področja strojnega učenja, analize podatkov in računalniškega vida. Trenutno končuje magistrsko delo na temo semantične segmentacije slik. V preteklosti je med drugim sodeloval tudi v ekipi za distribuirano upravljanje s podatki v CERN-u na projektu Rucio. ■ Lovro Šubelj je docent na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Diplomiral je leta 2008 na Fakulteti za matematiko in fiziko in Fakulteti za računalništvo in informatiko ter doktoriral leta 2013 na temo analize velikih omrežij. Je avtor ali soavtor več kot petdeset znanstvenih prispevkov in patentov ter urednik prestižnih mednarodnih znanstvenih revij. Njegovo preteklo delo je bilo izbrano kot izjemen znanstveni dosežek v Sloveniji ter predstavljeno na uglednih mednarodnih univerzah kot sta Stanford in UCSD. Sodeloval je že pri številnih uspešno zaključenih raziskovalnih in razvojnih projektih v sodelovanju s podjetji Petrol, Celtra, Optilab, Iskratel in drugimi. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 117 ZNANSTVENI PRISPEVKI B Effects of species extinction on ecosystems stability Učinki izumrtja vrst na stabilnost ekosistema 1Jaka Šircelj, 2Romi Koželj,1Lovro Šubelj 1University of Ljubljana, Faculty of Computer and Information Science, Večna pot 112, 1000 Ljubljana 2University of Ljubljana, Faculty of Mathematics and Physics, Jadranska ulica 19, 1000 Ljubljana sircelj.jaka@gmail.com; romi.kozelj@gmail.com; lovro.subelj@fri.uni-lj.si Abstract The food web describes the feeding relations between species in the ecosystem and makes possible the modelling of the dynamics between species. Based on existing data, we attempt to identify important species in the food web by examining the dynamic response after the removal of different species one at a time and observing the number of extinct species. This gives us a measure that estimates whether an extinction of a species would greatly affect its surrounding ecosystem and possibly also an estimate of trophic levels in the ecosystem. We also compare this measure as the baseline to other centrality measures in an attempt to establish a good and cost-efficient alternative. Keywords: Species importance, food web, ecosystem stability, population dynamics. Izvleček Omrežje plenilec-plen opisuje prehranjevalne odnose med vrstami v ekosistemu in omogoča modeliranje dinamike med vrstami. V članku skušamo z uporabo obstoječih podatkov najti pomembne vrste v tovrstnem omrežju. Uvedemo mero, ki definira pomembnost posamezne vrste in opisuje, kako močno bi izumrtje posamezne vrste vplivalo na njeno okolico. Njeno vrednost dobimo z opazovanjem dinamičnega odziva po odstranitvi vrste in s spremljanjem števila izumrlih vrst, ki ga taka odstranitev povzroči. S takšno mero lahko dobimo tudi oceno o strukturi tropskih nivojev v ekosistemu. Dobljeno mero, ki služi kot osnova primerjamo z ostalimi merami sre-diščnosti v upanju, da najdemo dobro in poceni alternativo. Ključne besede: pomembnost vrst, omrežje plenilec-plen, stabilnost ekosistemov, populacijska dinamika 1. INTRODUCTION An ecosystem of different species of flora and fauna can be described by the relations between these species, for example how they feed on each other. This information can be recorded by a network structure called a food-web. A food-web is a directed weighted network that describes relations between predators and their prey, where the weights are correlated to the intensity of the feeding relation between the predator and its prey. Food-webs are usually smaller networks consisting of 20 to 150 nodes. They also come with the initial biomasses of the species in the system, which is usually given in kcal per square meter or weight per square meter. Because food-webs give us a relation of how much one species feeds on another and what the size of each population is, we can use the data to define a population model, giving us a prediction on how each species population will change in time. Using existing food-web networks that describe how species interact and feed, we try to model their dynamics. Specifically, using a dynamic model, we test the system for weak 118 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability points. This information can tell us which species are most important for the stability of others, giving them a higher priority to preserve than other species that have a smaller impact on the system. The analysis can be done by simply removing a species from a stable network and observing how the system responds to the change, if any other species became extinct, or how many of them became extinct. Since this method takes some time for computations, we compare it to other centrality measures in hope of finding a method that gives similar results, but is also cheaper. In the paper we first do a short review of related work dealing with similar problems. Then, in the methods section, we propose our methods of determining the importance of species. We also describe other centrality measures we test and approaches of comparing them to our methods. In the results section, we first show an example of population dynamic. Then, we show the results of our methods and other centrality measures on different food-webs and compare the results. 2. RELATED WORK Gilljam et. al. (Gilljam, Curtsdotter, & Ebenman, 2015) dealt with similar extinctions that lead to instabilities, but expanding on this, evaluated what happens if the predators of the extinct species find a new prey or move to a prey that is less frequent in their diet, effectively making a link rewiring. First an observation was made that usually primary producers go extinct following by primary consumers and secondary consumers last. It has also been found that rewiring does not help the stability but only aggravates it. The negative effect was even stronger when predators were efficient in exploiting rare and new prey. Williams and Martinez (Williams & Martinez, 2000) predicted different structural properties of some complex food webs from freshwater habitats, freshwater-marine interfaces and terrestrial habitats using random model, cascade model and niche model. In the random model, any link among species occurs with the same probability . The cascade model assigns each species a random value drawn uniformly from the interval and each species has probability of consuming only species with values less than its own, where denotes connectance level, denotes number of actual links and number of all possible links. The niche model similarly assigns each species a randomly drawn niche value. The species are then constrained to consume all prey species within one range of values whose randomly chosen centre is less than the consumer's niche value. The parameters of all models were set to synthesize webs with empirically observed species number and connectance level . They calculated normalized error as difference between empirical properties and a model's mean, predicted by Monte Carlo simulations, divided by the standard deviation of the property's simulated distribution. Results showed the niche model to be the most accurate, the cascade model was over an order of magnitude worse, while the random model was the worst. The random model's large errors show, that simply matching an empirical web's and does little to account for empirical food-web properties. Palamara et. al. (Palamara, Zlatic, Scala, & Calda-relli, 2011) introduced weighted projection graphs that extend niche graphs by adding the possibility of weighted links. From comparing synthetic and real graphs properties they found some improvement. On top of this, they performed population dynamics evaluation described by the weights of the graphs, finding that the stability of the model decreases as its complexity increases. Stouffer et. al (Stouffer, Sales-Pardo, Sirer, & Ba-scompte, 2012) measured species' roles and their dynamic importance when embedded in their community network. They introduced a definition of species' roles based around the concept of network motifs, which provide a mesoscale characterization of community structure. They focused on communities made out of 3 node motifs, composed of 30 unique positions. To take into account dynamics, they associate a benefit to each position across all motifs, determined by how much community persistence increases or decreases when single motif is added to the network. For each species they calculated how many times it appears in each position, where they also weighted positions with their benefits. They searched for species that exhibit statistically similar motif profiles. Across the 2468 empirical species and 32 webs, they observe 54 distinct empirical roles. They were also interested if this result reflects an intrinsic property of each species, so they compared the relative importance of 150 species that occur in at least 2 of the 10 different networks and found that if species is important in one web, it is also important in other webs in which it appears. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 119 Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability Allesina and Pascual (Allesina & Pascual, 2009), similarly to our method, tried to evaluate the most important species that their extinctions cause extinction cascades. First they introduced a »root« node to the food-web that points to the primary producers and defined that a species goes extinct if it severs its reachability to it. Next they introduce an algorithm that in each step, removes a species from the food web according to the measure of choice and removes species that became extinct. The iteration stops when all species go extinct or are removed. For the methods of choice the authors propose two measures based on PageRank (Sergey & Page, 1998) and compare them to more basic measures, namely, degree, closeness, betweenes centrality and a dominators measure where node dominates node if all the paths from »root« contain . They compared results with a proposed »extinction area« measure, which returned the area under the plot of proportion of extinct species related to the proportion of removed nodes. Their results show that the eigenvector measures proved to give the fastest extinction sequences, beating the other measures in all given food-webs. 3. METHODS We denote as the biomass of species in time. The dynamics of species is modeled using the population equation where represents the number of species and denotes the linear rate with which the population of species is growing or dying regardless of its predators and prey. This can be interpreted as contribution from natural death and fertility of the species. The parameter denotes the relation between species and , which can be positive if is prey of or negative and the relation is flipped. The sign is inferred from the direction of the link in the network. This part of the relation can be interpreted as a model of encounters. If there are more species of and , their encounters are more probable, so the one will feed on the other more often, driving the numbers of the prey down and the numbers of the predator up, since more food is a positive force to the fertility. Before removing species and observing the response we want the initial network to be stable. To achieve this we specify the condition . This is done by simply correcting the parameters accordingly After we obtain a static system, we can start removing nodes to observe the response. We propose an algorithm which assesses the importance of a node, which we name Ratio (Algorithm 1). The algorithm uses the Euler method to perform the integration in time, while the count_dead method just counts how many species biomass came under a certain threshold, which is a user set parameter that determines the lower bound, where the species is not yet extinct. We set the threshold to 1% of the initial biomass. Note that during the integration, we remove species that fall below the threshold, since, according to the population equation, they can still recover even if their biomass is unreasonably small. Data : Input food-web Result: Dictionary of importances for each species importance = {} Initialize b_i so that dx/dt = 0 for i = 1... S do remove node i from the food-web new_x = integrate using the system of equations for a certain time and return final biomasses importance[i] = count_dead(new_x) / S add node i back into the food-web return importance Algorithm 1: Computation of importance for every species/node. 120 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability This counting technique might not be the best, since heavier species would die out when its biomass would go under a higher threshold, while lighter species such as plankton can still have high numbers even if its biomass is seemingly low. The Ratio measure is likely to give the same result for multiple species, since multiple species can lead to the same number of extinctions. To give species more variance in their importance we introduce another measure, named Area. Here, instead of just counting how many species die after the integration, we use the time plot of the ratio of remaining species along the time axis (example in Figure 1). We then calculate the area under each curve, normalized to the area where no species came to extinction. A small area close to 0 indicates rapid extinction, making the species that cause it very important, while an area of 1 indicates no extinctions at all. Our food-webs contain nodes »Input«, »Output« and »Respiration«, which we remove before we run our algorithms. The justification for this is that these three nodes serve as an external »force« on our system and it would be unreasonable to model the dynamics of external parameters. We also presume external forces just by the stability condition we specified by correcting parameters . This removal causes some other nodes to become isolated from the rest of the network. Since isolated nodes have no predators and no prey, their biomass would not change over time, so we removed them too. We define our methods Ratio and Area as base methods, since they are the most theoretically sound. We compare centrality measures PageRank, betwee-ness, closeness centrality and clustering coefficient with our proposed methods. PageRank (Sergey & Page, 1998) first assigns an equal amount of importance to each node and then iteratively calculates PageRank for each node according to the equation (3) where is the PageRank of the node , is the adjacency matrix, is the degree of out-going edges of node , is a damping parameter and is the number of nodes in a network. The basic idea of the algorithm is that importance is propagated trough the network where important nodes point to important nodes. We took the reversed graph when calculating PageRank, because species that »feed« others should be ranked higher so they should be successors of their predators, but in the case of food-webs the arcs are reversed. This can be better explained with a toy example where we have one prey/food source that, in the case of a food-web, points towards its predators that aren't connected to one another, essentially making a star-like structure. In this case the PageRank of the prey would be spread between its predators, making its rank the smallest. If we reverse the links, the opposite happens and the central node accumulates all of the PageRank from its predators, making it the most important, which it is, since if we remove it, all other species die out from the lack of a food source. gramdry Riftri "v. —•• \ removea: nanmets ju.jao) - removed: Raccoons (0.594) * removed: Snakes (0.697) \ \ \ \ 1 \ I \ \ l \ 1.0 : 0.8 ; 0.6 ■ 0.4 S 0.2 0.0 0.0 0.2 0.4 0.6 0.8 1.0 Figure 1: Plot of fraction of remaining species along the time of integration for the gramdry food-web. The area under each curve is used to evaluate the belonging species. The legend shows area results for »Panthers«, »Raccoons« and »Snakes«. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 121 Jaka ŠirceLj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability Betweeness centrality () gives a larger value to nodes that have a position such that they lay on a large number of shortest paths between other pairs of nodes in the graph. It is calculated using equation (7) = JL V ik n2 L-t gst St (4) where is the total number of shortest paths from to and is the number of paths going through . Closeness centrality (NetworkX, 2018) for a node is calculated by equation Ci = n - 1 (5) and the correlation coefficient matrix elements were calculated as Cu yjCn Cjj (8) where is the length of the shortest path from node to . Its justification is that a node should be more important if it is closer to the other nodes. Clustering coefficient for a node gives an information about local density of a network around that node. More precisely it tells what fraction of pairs of neighbours of node are connected to each other. It is calculated by equation (6) where is the degree of node , is the number of all possible pairs of neighbours of node , and represents the number of pairs of neighbours of node that are connected. If a node has degree 0 or 1, it doesn't have any pairs of neighbours, so its clustering coefficient is 0. We also compare our methods with two other measures, one that takes into account degrees of nodes and one that takes into account weights on links. The first one we calculated as degree of the node, normalized with number of all links in the network and the second one as sum of weights over all in-links and out-links of the node, normalized with sum of weights over all links in the network. Finally, we calculate correlations between all measures and show a correlation coefficient matrix with the measures on the axis (Figure 5). The correlations were calculated using the Pearson product-moment correlation coefficients Note that when performing these calculations we inverted our Area measure as so that we didn't have to deal with anti-correlations when comparing it with our Ratio measure. 4. RESULTS We found food-web data on the pajek website (Bata-gelj, 2004). For each food-web we analyzed, we first calculated to induce stability. When testing the Ratio measure on the CrystalC food-web we found that whatever species we remove, it causes extinction of several other species. The most important species in this network is »blacktip shark«, removal of which causes 11 other species to die out and the least important is »silverside«, which causes extinction of 6 other species. After cleaning the network we ended up with 20 nodes, not including the initially extinct species the »blacktip shark«. For these 20 nodes we plotted time dependency of 10s 105 io3 101 10- CrystalC, removed: blacktip shartt ....... mullet —- silverside / ----stingray . -ï-J / \ / / \ / 1 s —Y-------- s \ \ V. \ \ t s i 10c Figure 2: Changes of biomasses over time after removing node »blacktip shark« in the food-web CrystalC. Nodes »mullet« and »silverside« show how species die out over time, the same for »macrophytes«, which represents species that start oscillating too violently, while »stingray« demonstrates species that increases in size. 122 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability biomass changes and in Figure 2 showed the most interesting ones. For already mentioned food-web CrystalC and for the food-web gramdry, we calculated values of importance for each species in the network by 8 different methods. The most significant results are shown in Table 1 and in Table 2. Looking at the results for the CrystalC food-web, the Ratio measure gives an interesting observation. We can see that 5 groups of species form, each with the same rank. These groups roughly translate to the pyramidal structure of trophic levels of ecosystems, where we have apex predators, consumers, producers and decomposers. In our case, we have the »blacktip shark« as the apex predator, various fish as consumers, and plankton, invertebrates, microphytes and macrophytes forming a joint group of producers and decomposers. The last two groups feed on dead organic material called »detritus« which isn't a living organism, but can still be considered as the lowest level. Of course the ordering isn't perfect, for example the »goldspotted killifish« and similar small fish in the joint group with Ratio value of 0.45 should most likely belong to the consumers. Optimally, the joint group of producers and decomposers should also be split up. The »silverside« fish also belongs to the consumers and not in its separate and lowest level. In the Area measure, a similar observation of groups can be made, only the values are more varied and the clusters aren't immediately apparent. To better show trophic levels, we do an agglomerative hierarchical clustering and show its results (Figure Table 1: Species importance by different measures for the CrystalC food-web. Table shows all 21 species. The species are ordered by the results of our method using the Ratio score, while we also show what species placed in the first three places for other measures, including our score that uses the Area measure. species Ratio Area degree weights pagerank betweenness clustering closeness blacktip shark 0.60 0.606 (2) 0.024 0.000393 0.016 0.0000 0.000657 0.357 stingray 0.50 0.669 0.074 0.000111 0.016 0.0447 0.000037 0.465 striped anchovy 0.50 0.670 0.049 0.000023 0.016 0.0197 0.000094 0.540 (3) needlefish 0.50 0.669 0.111 0.000244 0.016 0.0842 0.000066 0.487 sheepshead killifish 0.50 0.669 0.086 0.000272 0.017 0.0552 0.000155 0.540 (3) longnosed killifish 0.50 0.668 (3) 0.049 0.000838 0.017 0.0000 0.000694 (2) 0.350 silver jenny 0.50 0.670 0.049 0.000021 0.016 0.0263 0.000124 0.540 (3) sheepshead 0.50 0.669 0.037 0.000056 0.016 0.0236 0.000338 0.363 pinfish 0.50 0.669 0.123 (3) 0.000322 0.027 0.2500 (3) 0.000073 0.487 gulf flounder 0.50 0.670 0.061 0.000017 0.016 0.3236 (2) 0.000012 0.434 microphytes 0.45 0.719 0.061 0.053924 0.053 0.0000 0.001176 (1) 0.000 2018 - številka 3 - letnik XXVI u P O R A B N A I N F O R M A TIKA 123 3). The clustering on Area performs even better than Ratio. The pyramidal structure remained, and what's more, small fishes split from the joint producers/decomposers group. We only find a few stragglers in the results such as »mullet«, which shouldn't be at the top and the fish »silverside«, which shouldn't belong to the joint level, although now it is not strongly connected to it. Figure 3: A dendrogram visualizing the agglomerative clustering on the CrystalC food-web, using the Ward measure. The dendrogram is not plotted fully since we are not interested in its top-most branches. The groups are shown with different shades of gray for the lines. As for the other measures, we didn't see much correlation, they give »detritus« the largest score, since it has the most in-going edges. Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability species Ratio Area degree weights pagerank betweenness clustering closeness macrophytes 0.45 0.715 0.012 0.543455 (2) 0.173 (2) 0.0000 0.000000 0.000 Zooplankton 0.45 0.716 0.098 0.025203 0.067 0.0000 0.000273 0.512 benthic invertebrates 0.45 0.716 0.172 (2) 0.368955 (3) 0.131 (3) 0.0973 0.000340 0.512 bay anchovy 0.45 0.681 0.098 0.000538 0.032 0.0210 0.000130 0.540 (3) goldspotted killifish 0.45 0.672 0.098 0.000358 0.017 0.0763 0.000171 0.555 (2) moharra 0.45 0.676 0.098 0.001093 0.022 0.0000 0.000271 0.540 (3) mullet 0.45 0.556 (1) 0.086 0.006728 0.033 0.0500 0.000686 (3) 0.526 gulf killifish 0.40 0.685 0.123 (3) 0.001021 0.018 0.0078 0.000149 0.487 detritus 0.40 0.765 0.370 (1) 0.993402 (1) 0.237 (1) 0.7197 (1) 0.000235 1.000 (1) silverside 0.30 0.703 0.111 0.003026 0.046 0.0000 0.000430 0.540 (3) Table 2: Species importance by different measures for the gramdry food-web. Table shows only the most significant species out of 66. The ordering is shown in the same way as in Table 1. species Ratio Area degree weights pagerank betweenness clustering closeness Panthers 0.984 0.396 0.0100 0.000000 0.0056 0.18870 0.000000 0.439 Nighthawks 0.984 0.394 0.0088 0.000000 0.0056 0.00000 0.000001 0.343 Tadpoles 0.969 0.374 0.0113 0.000000 0.0056 0.03966 0.000003 0.520 Mink 0.969 0.403 0.0592 0.000000 0.0056 0.15481 0.000000 0.714 (3) Bobcat 0.969 0.404 0.0100 0.000000 0.0056 0.15336 0.000001 0.457 Ducks 0.969 0.403 0.0390 0.000000 0.0056 0.00000 0.000000 0.460 Sediment Carbon 0.969 0.149 (1) 0.0895 (2) 0.551595 (1) 0.0657 (3) 0.12981 0.000238 0.928 (2) Labile Detritus 0.969 0.191 (2) 0.0327 0.393440 (3) 0.0665 (2) 0.01466 0.000876 (2) 0.361 Mesoinverts 0.953 0.245 (3) 0.0643 (3) 0.001846 0.0562 0.06010 0.000058 0.537 Other Small Fishes 0.953 0.409 0.0327 0.000000 0.0056 0.25481 (3) 0.000001 0.537 Otter 0.953 0.589 0.0390 0.000013 0.0056 0.00000 0.000002 0.515 Living Sediments 0.938 0.497 0.0327 0.142788 0.0631 0.00000 0.001198 (1) 0.485 Macrophytes 0.938 0.462 0.0252 0.039412 0.0572 0.00000 0.000099 0.000 Floating Veg. 0.938 0.461 0.0163 0.055918 0.0331 0.00000 0.000138 0.000 Large frogs 0.938 0.593 0.0264 0.000004 0.0056 0.00000 0.000002 0.424 Medium frogs 0.938 0.593 0.0239 0.000005 0.0063 0.00000 0.000002 0.398 Small frogs 0.938 0.594 0.0264 0.000001 0.0058 0.00048 0.000001 0.398 Alligators 0.938 0.594 0.0529 0.000004 0.0062 0.04976 0.000001 0.613 Rats&Mice 0.938 0.593 0.0176 0.000054 0.0061 0.01298 0.000023 0.419 Raccoons 0.938 0.594 0.0290 0.000018 0.0056 0.09976 0.000005 0.492 Opossum 0.938 0.567 0.0214 0.000138 0.0056 0.00000 0.000027 0.565 W-T Deer 0.923 0.589 0.0088 0.000030 0.0058 0.00000 0.000081 0.030 Turtles 0.907 0.603 0.0378 0.000020 0.0056 0.01418 0.000005 0.550 Periphyton 0.876 0.710 0.0239 0.316464 0.1704 (1) 0.00000 0.000497 (3) 0.000 Bitterns 0.784 0.530 0.0353 0.000000 0.0056 0.33317 (2) 0.000000 0.460 Refractory Detritus 0.784 0.499 0.1021 (1) 0.480765 (2) 0.0438 0.61995 (1) 0.000142 0.970 (1) Freshwater Prawn 0.676 0.476 0.0428 0.000322 0.0222 0.00000 0.000039 0.371 Snakes 0.446 0.697 0.0378 0.000090 0.0062 0.00000 0.000010 0.477 LiZards 0.353 0.745 0.0126 0.000023 0.0066 0.00000 0.000027 0.365 Large Aquatic Insects 0.307 0.794 0.0504 0.000068 0.0095 0.03029 0.000007 0.363 124 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability a Ratio b Closeness Figure 4: Visualization of the CrystalC food-web, where nodes are positioned such that their locations roughly relate to their trophic levels. We use two metrics to adjust the node size, one is our algorithm using the Ratio metric and the other is closeness. Our methods also show promising, albeit not perfect, results in the gramdry food-web (Table 2). Again, using Ratio, the predators, such as »Panther«, »Bobcat« and »Nighthawks« proved to be most important, and smaller animals being less important. The biggest error in this web was with small organisms such as »Mesoinverts« and »Macrophytes« and with sediments like »Labile Detritus« and »Sediment Carbon«, which scored high, especially in the Area measure, but should be in the lowest trophic levels. All other measures failed to predict the same importance of species as our methods did. This was the same both for CrystalC and gramdry food-web. The pyramidal structure of the trophic levels is also apparent only in our methods. We show the difference in Figure 4, where we visualize the CrystalC food-web, so that species are ordered in the pyramidal structure, with sediments and food source species at the bottom and predators at the top. We then make node size correlated with the specified measure. The visualization shows that Area brings clear differentiation into levels while closeness doesn't. We also tried to remove »detritus« from CrystalC in the preparation step, since it is not a living organism. Unfortunately this brought more problems than advantages, since the population dynamic behaved slower and the pyramidal structure broke. Finally, we plot the correlation coefficient matrices, comparing correlations between the 8 measures. In Figure 5, we show results for two already discussed food-webs and also for Florida and Narragan. After cleaning, the Florida food-web has 125 species and Narragan has 32. Our two measures Ratio and Area are unsurprisingly correlated, since they are both derived from the same information on the population dynamics of species. On the other hand, they are very uncorrelated to all other measures, showing that they aren't a viable choice of determining the importance of species. In the other methods of measuring importance, we also see some clustering. For example, in all cases PageRank and the weights measure are very correlated, while, interestingly, degree and weights aren't for these food-webs. This is because the weights for different edges differ so much that any correlation with degree is broken. 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 125 Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability Figure 5: Correlation coefficient matrix depicting correlations between measures R: Ratio (ours), A: Area (ours), d: degree, w: weights, p: PageRank, b: betweenness, clu: clustering clo: closeness. 5. DISCUSSION We have introduced an algorithm that uses food-web information about biomass flow to make a dynamic model of the population and gives two measures of importance to individual species, Ratio and Area. The Ratio measure is correlated with the importance of species and Area is anti-correlated. For both measures, species with higher importance would make a greater impact on the ecosystem if it would come to its extinction. The results are promising, especially since the results of Ratio and Area for CrystalC food-web show a clear pyramidal structure of the species, where Area is slightly better since it brings more differentiation inside clusters. These results indicate that the measures can be taken as a baseline for evaluating species importance. They can also be used for species clustering into different trophic levels. Similar pyramidal structure can be observed in the gram-dry food-web, although not perfect, giving too much importance to microorganisms. More work should be done on optimizing parameters of the methods, making the model as dynamic as possible, while keeping precision in the numerical computations, thus solving cases where no activity occurs because of a too small time step. Using an adaptive time step would also be helpful. Changing the time step as needed, instead of keeping a constant one, would help lower computational time for cases where no activity occurs for longer periods of time, since solving such cases with a small time step is very time consuming. Also, more thought should be put into determining the stopping criteria of the integration. If we achieve stability at the end of the integration, the results should improve too, moving singletons like »mullet« or »silverside« into more appropriate trophic levels. The correlation matrices showed that finding a cheaper alternative to our measures was unsuccessful, which is disheartening since our method is very time consuming. A faster alternative is still quite nee- 126 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Jaka Šircelj, Romi Koželj, Lovro Šubelj: Effects of species extinction on ecosystems stability ded, although improving parameters can also speed up computations. 6. REFERENCES [1] Allesina, S., & Pascual, M. (2009, September). Googling Food Webs: Can an Eigenvector Measure Species' Importance for Coextinctions? PLOS Computational Biology, 5, 1-6. doi:10.1371/journal.pcbi.1000494 [1] Batagelj, V. (2004, June 13). Pajek datasets. Retrieved from http://vlado.fmf.uni-lj.si/pub/networks/data/bio/foodweb/fo-odweb.htm [1] Gilljam, D., Curtsdotter, A., & Ebenman, B. (2015). Adaptive rewiring aggravates the effects of species loss in ecosystems. Nature Communications, 6, 8412. doi:10.1038/ncomms9412 [1] NetworkX. (2018, September 2). NetworkX Refrence. Retrieved from closeness_centrality: https://networkx.github.io/do-cumentation/networkx-1.10/reference/generated/networkx. algorithms.centrality.closeness_centrality.html Jaka Šircelj je diplomiral iz fizike na Fakulteti za matematiko in fiziko Univerze v Ljubljani, ter trenutno zaključuje magistrski študij programa računalništvo in informatika na Fakulteti za računalništvo in informatiko Univerze v Ljubljani, kjer se največ posveča strojnemu učenju, analizi omrežij, umetni inteligenci, ter računalniškemu vidu. V preteklosti je delal tudi na Institutu Jožefa Stefana na odseku Fizike nizkih in srednjih energij. ■ Romi Koželj je diplomirala iz fizike na Fakulteti za matematiko in fiziko Univerze v Ljubljani. V sodelovanju z Agencijo RS za okolje se je med študijem fizike nekaj časa raziskovalno ukvarjala s področjem seizmologije. Trenutno je študentka na magistrskem programu Računalništvo in informatika na Fakulteti za računalništvo in informatiko Univerze v Ljubljani, kjer poleg študija nabira izkušnje s sodelovanjem pri raznih projektih. ■ Lovro Šubelj je docent na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Diplomiral je leta 2008 na Fakulteti za matematiko in fiziko in Fakulteti za računalništvo in informatiko ter doktoriral leta 2013 na temo analize velikih omrežij. Je avtor ali soavtor več kot petdeset znanstvenih prispevkov in patentov ter urednik prestižnih mednarodnih znanstvenih revij. Njegovo preteklo delo je bilo izbrano kot izjemen znanstveni dosežek v Sloveniji ter predstavljeno na uglednih mednarodnih univerzah kot sta Stanford in UCSD. Sodeloval je že pri številnih uspešno zaključenih raziskovalnih in razvojnih projektih v sodelovanju s podjetji Petrol, Celtra, Optilab, Iskratel in drugimi. [1] Palamara, G., Zlatic, V., Scala, A., & Caldarelli, G. (2011, January). Population Dynamics on Complex Food Webs. Advances in Complex Systems, 14, 635-647. doi:10.1142/ S0219525911003116 [1] Sergey, B., & Page, L. (1998, April). The Anatomy of a Large-scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30, 107-117. doi:10.1016/S0169--7552(98)00110-X [1] Stouffer, D. B., Sales-Pardo, M., Sirer, M. I., & Bascompte, J. (2012, March). Evolutionary conservation of species's roles in food webs. Science, 335, 1489-1492. doi:10.1126/scien-ce.1216556 [1] Williams, R. J., & Martinez, N. D. (2000). Simple rules yield complex food webs. Nature, 404, 180-183. doi:10.1038/35004572 ■ 2018 - številka 3 - letnik XXVI uporabna INFORMATIKA 127 INFORMACIJE B Iz Islovarja Islovar je spletni terminološki slovar informatike, ki ga objavlja jezikovna sekcija Slovenskega društva INFORMATIKA na naslovu http://www.islovar.org. Tokrat predstavljamo posebno rešitev oblik ženskega spola v zbirki »kadri«. Vabimo vas, da v Islovar prispevate svoje pripombe, predloge ali nove izraze. diréktor informatike -ja - m diréktorica informatike -e - ž (angl. chief information officer, CIO) kdor je odgovoren za informatiko v organizaciji informatik -a m informatičarka -e ž (angl. information specialist) strokovnjak za informatiko kibernétik -a m kibermtičarka -e ž (angl. cybernetic) strokovnjak za kibernetiko omrežni skrbnik -ega -a m omrežna skrbnica -e -e ž (angl. network administrator) kdor skrbi za delovanje omrežja; sin. skrbnik omrežja podatkovni analitik podatkovna analitičarka -e -e ž (angl. data analyst) strokovnjak, ki analizira podatke programêr -rja m programêrka -e ž (angl. coder, programmer) kdor piše kodo, opredeljeno v specifikacijah programêr analitik -rja -a m programêrka analitičarka -e -e ž (angl. programmer analyst) kdor proučuje potrebe uporabnikov in razvija programsko opremo; prim. sistemski analitik razvijalec -lea m razvijalka -e ž (angl. developer) kdor razvija programske rešitve razvijalec cêlnih sistémov -lea----m razvijalka čelnih sistémov -e----ž (angl. front-end developer) razvijalec, ki razvija čelni del računalniških sistemov; prim. razvijalec zalednih sistemov 128 uporabna INFORMATIKA razvijalec zalednih sistemov -lea----m razvijalka zalednih sistemov -e----ž (angl. back-end developer) razvijalec, ki razvija zaledne dele sistema; prim. razvijalec čelnih sistemov sistemski analitik -ega -a m sistemska analitičarka -e -e ž (angl. systems analyst) računalničar, ki izvaja sistemsko analizo; prim. programer analitik skrbnik podatkovne baze -a----m skrbnica podatkovne baze -e----ž (angl. database administrator) kdor skrbi za delovanje podatkovne baze skrbnik spletišča -a -- m skrbnica spletišča -e -- ž (angl. webmaster) kdor skrbi za delovanje spletišča in komunicira z uporabniki; sin. spletni skrbnik spletni razvijalec -ega -a m spletna razvijalka -e -e ž (angl. web developer) kdor razvija spletne strani in spletne aplikacije spletni skrbnik -ega -a m spletna skrbnica -e -e ž (angl. webmaster) kdor skrbi za delovanje spletišča in komunicira z uporabniki; sin. skrbnik spletišča univerzalni razvijalec -ega -- m univerzalna razvijalka -e -e ž (angl. full-stack developer) razvijalec, ki obvlada razvoj vseh plasti (2) programskih rešitev 2018 - številka 3 - letnik XXVI Včlanite se v Slovensko društvo INFORMATIKA Pristopna izjava za članstvo v Slovenskem društvu INFORMATIKA Pravne osebe izpolnijo samo drugi del razpredelnice Ime in priimek Datum rojstva Stopnja izobrazbe srednja, višja, visoka Naziv prof., doc., spec., mag., dr. Domači naslov Poštna št. in kraj Ulica in hišna številka Telefon (stacionarni/mobilni) Zanimajo me naslednja področja/sekcije9 Zaposlitev člana oz. člana - pravna oseba Podjetje, organizacija Kontaktna oseba Davčna številka Poštna št. in kraj Ulica in hišna številka" Telefon Faks E-pošta □ jezik □ informacijski sistemi □ operacijske raziskave □ seniorji □ zgodovina informatike □ poslovna informatika □ poslovne storitve □ informacijske storitve □ komunikacije in omrežja □ softver □ hardver □ upravna informatika □ geoinformatika □ izobraževanje kraj, datum podpis Pošto društva želim prejemati na domači naslov / v službo. Članarina znaša: 18,00 €-redna 7,20 € - za dodiplomske študente in seniorje (ob predložitvi dokazila o statusu) 120,00 € - za pravne osebe Članarino, ki vključuje glasilo društva - revijo Uporabna informatika, bom poravnal sam / jo bo poravnal delodajalec. DDV je vključen v članarino. Naročilnica na revijo UPORABNA INFORMATIKA Naročnina znaša: 35,00 € za fizične osebe 85,00 € za pravne osebe - prvi izvod 60,00 € za pravne osebe - vsak naslednji izvod 15,00 € za Študente in seniorje (ob predložitvi dokazila o statusu) DDV je vključen v naročnino. ime in priimek ali naziv pravne osebe in ime kontaktne osebe davčna številka, transakcljski račun naslov plačnika naslov, na katerega želite prejemati revijo (če je drugačen od naslova plačnika) telefon/telefaks elektronska pošta Podpis Datum 130 uporabna INFORMATIKA 2018 - številka 3 - letnik XXVI Izpitni centri ECDL ECDL (European Computer Driving License), ki ga v Sloveniji imenujemo evropsko računalniško spričevalo, je standardni program usposabljanja uporabnikov, ki da zaposlenim potrebno znanje za delo s standardnimi računalniškimi programi na informatiziranem delovnem mestu, delodajalcem pa pomeni dokazilo o usposobljenosti. V Evropi je za uvajanje, usposabljanje in nadzor izvajanja ECDL pooblaščena ustanova ECDL Fundation, v Sloveniji pa je kot član CEPIS (Council of European Professional Informatics) to pravico pridobilo Slovensko društvo INFORMATIKA. V državah Evropske unije so pri uvajanju ECDL močno angažirane srednje in visoke šole, aktivni pa so tudi različni vladni resorji. Posebno pomembno je, da velja spričevalo v 148 državah, ki so vključene v program ECDL. Doslej je bilo v svetu izdanih že več kot 11,6 milijona indeksov, v Sloveniji več kot 17.000, in podeljenih več kot 11.000 spričeval. Za izpitne centre v Sloveniji je usposobljenih osem organizacij, katerih logotipe objavljamo. LJUDSKA UNIVERZA MURSKA SOBOTA ACADEMIA • • • • • Pogledi v zgodovino Janez Grad RAZVOJ RAČUNALNIŠTVA IN INFORMATIKE NA UNIVERZI V LJUBLJANI, S POUDARKOM NA POMENU RRC IN RCU • • • • • • • • • • • • • • • Znanstveni prispevki • • • • • Ciril Bohak, Jože Guna, Peter Škrlj, Alja Isakovič, Matija Marolt A USABILITY COMPARISON OF INPUT DEVICES FOR PRECISE AND INTUITIVE INTERACTION WITH 3D VISUALIZATIONS Vitjan Zavrtanik, Lovro Šubelj COMMUNITY DETECTION IN SLOVENE PUBLIC SPENDING Jaka Šircelj, Romi Koželj, Lovro Šubelj EFFECTS OF SPECIES EXTINCTION ON ECOSYSTEMS STABILITY Informacije IZ ISLOVARJA 1 ISSN 1310-lflflE 9771318188001