ELEKTROTEHNIŠKI VESTNIK 88(5): 273-278, 2021 PREGLEDNI ZNANSTVENI ČLANEK Odkrivanje skupnosti v električnih omrežjih Krista Rizman Žalik Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Koroška cesta 45, 2000 Maribor, Slovenija E-pošta: krista.zalik@um.si Povzetek. V preglednem članku opišemo metode odkrivanja skupnosti, ki se poleg drugih delitvenih algoritmov uporabljajo za delitev električnih omrežij. Električno omrežje je kompleksno omrežje. Kompleksna omrežja tvorijo strukturo skupnosti. Skupnost sestavljajo vozlišča omrežja, ki so gosto povezana med sabo in redko z drugimi vozlišči skupnosti. Delitev kompleksnih omrežij z odkrivanjem skupnosti je pomembno raziskovalno področje v teoriji kompleksnih omrežij. Odkrivanje skupnosti je optimizacijski problem s ciljem poiskati skupnosti, ki pripadajo omrežju ali grafu, ob predpostavki, da imajo vozlišča iste skupnosti enake lastnosti in skupne značilnosti ali funkcionalne odnose v omrežju. V električnih omrežjih se uporablja večina obstoječih algoritmov odkrivanja skupnosti s prilagoditvami za električno omrežje. Algoritmi odkrivanja skupnosti so različno primerni in učinkoviti za delitve električnih omrežij. Ključne besede: električno omrežje, kompleksno omrežje, odkrivanje skupnosti Community Detection in Power Grids The paper reviews community detection methods used besides other partition algorithms for power grid partitioning. The power grid is a complex network. A complex network forms a community structure. There are many edges between community nodes and relatively few of those connecting the vertices of different communities. Community detection is an optimization problem. Its goal is to detect communities that belong to a network or graph in which nodes of a particular community in the same community share properties of the same characteristics or functional relationships. Power grids use adaptable community detection algorithms of various suitability rates used in power grid partitioning. The paper presents types and adaptations of various community detection algorithms used in power grid partitioning. Keywords: power grid, complex network, community detection 1 UVOD Razumna delitev omrežij je pomemben predpogoj tudi za učinkovito delovanje in nadzor elektroenergetskih omrežij. Namen razdelitve električnega omrežja je olajšati delovanje, nadzor in upravljanje regionalnega električnega omrežja. Inženirji lahko pametna energetska omrežja opremijo s sposobnostjo varovanja problematičnih delovnih pogojev, in tako preprečijo izpade [1]. Z uporabo teorije kompleksih omrežij in metod odkrivanja skupnosti lahko delimo električna in druga omrežja, ki jih predstavimo z množico vozlišč in robov [2, 3]. Kompleksna omrežja tvorijo strukturo skupnosti. Skupnost sestavljajo vozlišča omrežja, ki so gosto povezana med sabo in redko z drugimi vozlišči skupnosti. Z algoritmi odkrivanja skupnosti lahko razdelimo velika omrežja v manjša, ki jih je lažje nadzirati, in tako povečamo robustnost velikih sistemov [4]. Raziskave infrastrukture električnega omrežja na osnovi kompleksne mrežne teorije [5] predstavijo električno omrežje z vozlišči omrežja, ki so proizvajalci električne energije, razdelilne transformatorske postaje in porabniki, medtem ko povezave med vozlišči predstavljajo daljnovode. Razdelilna transformatorska postaja, ki je omenjena kot vozlišče omrežja, zajema tudi transformatorje. Če se te izvzame iz vozlišč in se jih obravnava kot povezave, lahko v analizo zanesljivosti obratovanja omrežja poleg vodov zajamemo tudi transformatorje. Metode odkrivanja skupnosti lahko v analizi električnih omrežij uporabimo tudi kot dopolnilo običajnim metodam razdelitve električnega omrežja. Večina metod za odkrivanje skupnosti v električnih omrežjih dopolni klasične metode odkrivanja skupnosti in temelji samo na topoloških značilnostih omrežja. Tako večina metod ne upošteva funkcij skupnosti, zato ne odražajo v celoti električnih značilnosti električnih omrežij. Na primer v [6] so indeks podobnosti predlagali za dodelitev vsakega vozlišča k skupnosti, ki ji je vozlišče najbolj podobno, vendar ta ne odraža v celoti električnih značilnosti električnih omrežij. Ob zanemarjanju kompleksnih električnih lastnosti se generatorji in obremenitve obravnavajo kot vozlišča, vodi pa kot povezave med vozlišči. Povezave med vozlišči se obravnavajo kot podobnost. Prejet 10. junij, 2021 Odobren 30. september, 2021 274 RIZMAN V raziskovanju električnih omrežij večina prilagodi obstoječe algoritme delitve in iskanja skupnosti za delitev električnih omrežij. Omrežje obravnavajo kot množico vozlišč in povezav med njimi. Za skupnost velja, da ima več notranjih povezav med vozlišči skupnosti, kot je povezav z vozlišči drugih skupnosti. Če vzamemo vozlišča brez povezav kot točke in razdaljo med njimi opišemo z matriko razdalj ali matriko podobnosti, pa lahko za grupiranje teh točk uporabimo algoritme gručenja. Gruča je množica točk, ki so si veliko bliže, kot je razdalja do točk sosednih gruč. Popularne metode gručenja za delitve v analizi električnih omrežij so metode gručenja, kot sta K-means, K-medoids, ter njihove razširitve [7, 8] in spektralno gručenje [9, 10]. Predlagane so bile predvsem prilagoditve klasičnih algoritmov za odkrivanje skupnosti in gruč v električnih omrežjih. O njih in njihovi učinkovitosti v električnih omrežjih razpravljamo v naslednjih poglavjih. 2 SPEKTRALNE METODE GRUČENJA Hierarhično spektralno iskanje gruč vozlišč lahko uporabimo tudi za delitev električnega omrežja. V [11] so uporabili admitanco vodov in povprečen pretok energije v podanem času kot uteži, ki opišejo statično interno strukturo in dinamične lastnosti sistema, ter pokazali, da je hierarhično spektralno gručenje učinkovito za delitev električnega omrežja. Spektralno gručenje dela na grafu, ki je opisan z n vozlišči v 1, v 2,…, v n s funkcijo podobnosti parov S, ki tvorijo simetrično in ne negativno matriko (i. e., S (v i , v j) = S (v j, v i) ≥ 0, ∀i, j = 1, … n). Spektralno gručenje vključuje metode in tehnike, ki razdelijo vozlišča v gruče z uporabo lastnih vrednosti in lastnih vektorjev matrike. Spektralno gručenje je sestavljeno iz pretvorbe začetnega niza objektiv v niz točk v prostoru, katerih koordinate so elementi lastnih vektorjev. Niz točk nato razdelimo v skupnosti s standardnimi tehnikami, kot je združevanje v gruče K-means [12]. Zamenjava začetnih vozlišč z matriko podobnosti z lastnimi vrednostmi in lastnimi vektorji matrike omogoča boljše deljenje vozlišč v gruče. Ker ima spektralno gručenje zaradi uporabe spektra (lastnih vrednosti) matrike podobnosti za zmanjšanje dimenzionalnosti kompleksnost O(n 3 ), je uporabno za manjše podatkovne množice. 3 ODKRIVANJE SKUPNOSTI Z GENETSKIMI ALGORITMI Raziskave so pokazale tudi učinkovitost evolucijskih algoritmov za delitev električnega omrežja [13, 14]. Evolucijski algoritmi so algoritmi, ki z evolucijskim procesom rešujejo globalne optimizacijske probleme. Evolucijski algoritmi so sestavljeni iz populacije posameznikov, ki se kontinuirano in selektivno razvija, dokler ni izpolnjen pogoj končanja razvoja. Najbolj uporabljeni evolucijski algoritmi so genetski algoritmi (GA) [15]. GA posnemajo naravno selekcijo in razvijajo populacije individualnih rešitev problema, dokler ni izpolnjen pogoj končanja. Najboljšo rešitev vzamemo kot končno rešitev. GA se razlikujejo po uporabljeni predstavitvi, ki je lahko binarna ali realna. GA uporabljajo različne mutacije in križanja, prav tako imajo parametri, kot sta velikost populacije in število iteracij, bistven vpliv na učinkovitost. Uporaba genetskih algoritmov v več visokonapetostnih prenosnih omrežjih na nacionalni ravni kaže učinkovitost genetskih algoritmov za odkrivanje skupnosti v mednarodnih prenosnih električnih omrežjih [13]. Avtorji so primerjali dva genetska algoritma za iskanje skupnosti v visokonapetostnih prenosnih omrežjih na nacionalni ravni. Prvi je MIGA – Modularni in izboljšan genetski algoritem (The Modularity and Improved Genetic Algorithm) [16]. Algoritem uporablja modularnost (Q) kot optimizacijsko funkcijo in število skupnosti kot vhodni parameter za povečanje točnosti odkrivanja skupnosti. MIGA uporablja tudi metodo postopnega ohlajanja (angl. Simulated Annealing) [17] za lokalno strategijo iskanja. Drugi algoritem GGA+ (The Generational Genetic Algorithm) [18] vključuje varno in uravnoteženo inicializacijo, ki priredi največje število vozlišč vsaki skupnosti. Algoritem izbere vozlišče in njegove sosede za vsako skupnost, dokler ne doseže največje velikosti skupnosti. Če je sosedov manj, kot je največja velikost skupnosti, vzame drugo vozlišče, ki še ni bilo v skupnosti, in njegove sosede. Algoritem ponavlja izbiro vozlišč, dokler ne doseže maksimalne skupnosti. Zahtevnost algoritma MIGA je manjša kot z eksperimentom dokazana zahtevnost za algoritem MA, iz katerega izhaja in je O(m α ) z α ≈ 1.3. Algoritem GGA+ uporablja genetsko operacijo križanja. Drugo izbrano vozlišče je tisto vozlišče iz druge skupnosti, ki je najbolj povezano z dejansko skupnostjo, ki mu pripada prvo vozlišče. Ta operator ohranja ravnovesje števila vozlišč med skupnostmi. Operator mutacije uporabi vozlišča v ciljni skupnosti, ki se razlikujejo od vozlišč dejanske skupnosti. Operatorji omogočajo prehod ali izmenjavo vozlišč med skupnostmi in uporabljajo funkcijo modularnosti kot optimizacijsko funkcijo. Rezultate obeh metod, MIGA in GGA+, ovrednoti vrednost modularnosti (Q) enačba (1) [19]. 𝑄 = 1 2𝑀 ∑ (𝑎 𝑖𝑗 − 𝑘 𝑖 𝑘 𝑗 2𝑀 ) 𝛿 (𝑖 ,𝑗 ) 𝑛 𝑖 ,𝑗 (1) M predstavlja skupno število robov v omrežju, i in j predstavljata dve vozlišči omrežja; k i in k j sta stopnji (število sosedov i-tega in j-tega vozlišča); a ij je element matrike sosednosti, ki ima vrednost 1, če obstaja ODKRIVANJA SKUPNOSTI V ELEKTRIČNIH OMREŽJIH 275 povezava med vozliščema i in j; in δ(i, j) opiše povezavo med i-tim in j-tim vozliščem, tako da ima za povezani vozlišči i in j vrednost 1, sicer 0. Modularnost je najpogosteje uporabljena funkcija v odkrivanju skupnosti tudi zaradi svoje preprostosti in hitrega izračuna. Je numerična vrednost, ki določa kvaliteto skupnosti in opiše, koliko večja je povezanost vozlišč skupnosti, kot je naključna povezanost. Torej, večja je vrednost modularnosti, bolj realna je struktura skupnosti. Izvedena analiza v viru [13] o uporabi obeh zgoraj opisanih genetskih algoritmov za odkrivanje skupnosti v mednarodnih prenosnih omrežjih je pokazala večjo učinkovitost algoritma GGA+ z boljšo srednjo vrednostjo in standardnim odklonom v vseh testnih primerih ne glede na število odkritih skupnosti. Rezultati so pokazali tudi, da čim večje je električno omrežje, večja je prednost GGA+ pred MIGA. Standardni odklon GGA+ za vse teste je manjši kot za MIGA, kar kaže na večjo robustnost GGA+. Genetske algoritme izboljšajo memetski, ki v selekcijo ali začetno populacijo vključijo možne populacije, torej dodatno znanje in tudi druge algoritme optimizacije. Na primer v [13] avtorji predlagajo hibridni algoritem, ki dopolni namenski operator križanja z večstopenjskim postopkom lokalne optimizacije. 4 DELITVENE METODE GRUČENJA Metode delitve grafov razdelijo vozlišča grafov v skupnosti, tako da je število povezav med vozlišči, ki pripadajo različnim skupnostim čim manjše. Med prvimi algoritmi je bil algoritem Kernighan-Lin, ki ga pogosto uporabljamo skupaj z drugimi za delitev omrežij [20]. Motivacija za algoritem je bila delitev elektronskih vezij na različna tiskanja vezja, ki zahtevajo čim manj povezav. Algoritem optimizira funkcijo, ki predstavlja razliko med številom robov znotraj skupnosti in številom robov med vozlišči različnih skupnosti. Algoritem začne z začetno delitvijo grafa v dve skupnosti; nato enako število vozlišč zamenja med dvema skupnostnima, tako da ima optimizacijska funkcija največji prirastek. Zamenjujemo lahko tudi posamezno vozlišče. Da se algoritem izogne lokalnemu maksimumu, izvede zamenjave, ki zmanjšajo optimizacijsko funkcijo. Po vrsti zamenjav z negativnim in s pozitivnim prirastom izberemo delitev grafa z največjo vrednostjo optimizacijske funkcije in jo uporabimo kot začetno točko nove iteracije delitve grafa. Algoritem Kernighan- Lin ima časovno zahtevnost O(n 2 log n) (n je število vozlišč) ob predpostavki, da izvede konstantno število zamenjav v vsaki iteraciji. Časovno najzahtevnejša je izbira vozlišč za zamenjavo zaradi računanja povečanja ali pomanjšanja vrednosti optimizacijske funkcije za vsak par iz množice vozlišč za zamenjavo. Na redkih grafih lahko z dodatno hevristiko zmanjšamo zahtevnost na O(n 2 ). Particije so odvisne od začetne delitve, in če je ta slaba, je tudi rezultat slab. Algoritem se uporabi za izboljšanje skupnosti, ki smo jih našli z drugimi metodami. Slabost algoritmov delitve grafov za odkrivanje skupnosti je zahtevan vnos števila skupnosti in v nekaterih primerih celo njihove velikosti. Tudi delitveno gručenje zahteva informacijo o številu gruč (k). K-means [12] je pogosto uporabljena delitvena metoda. Vsako vozlišče grafa je točka v metričnem prostoru in med temi točkami definiramo razdaljo. Razdalja je lahko tudi merilo različnosti med vozliči. Točke in s tem vozlišča razdelimo v skupnosti tako, da maksimiramo ali minimiziramo stroškovno funkcijo – razdaljo točk do središča skupnosti, ki ji pripada (enačba 2). ∑ ∑ ‖𝑣 𝑗 − 𝑐 𝑖 ‖ 2 𝑣 𝑗 ∈𝑆 𝑖 𝑘 𝑖 =1 (2) v j je točka iz gruče S i s središčem c i . Kompleksnost algoritma K-means je O(n 2 ), kjer je n število točk. Te metode odkrivanja skupnosti v kompleksnih mrežah temeljijo na topoloških lastnostih skupnosti in ne upoštevajo funkcij skupnosti, čeprav so te pomembne. Namesto razdalje lahko oblikujemo indeks podobnosti, ki meri bližino med različnimi vozlišči kot v [6], toda še vedno ne upoštevamo električnih lastnosti električnega omrežja. To je očitna slabost uporabe klasičnih metod gručenja. 5 HIBRIDNE METODE DELITVENIH ALGORITMOV IN GENETSKIH ALGORITMOV Za pohitritev in izboljšanje rezultatov lahko pred uporabo genetskih algoritmov poiščemo začetne populacije z drugimi algoritmi. Tako hibridna metoda za delitev električnega omrežja uporabi algoritem K-means in evolucijski algoritem za razdelitev električnih omrežij za optimizacijo več-atributne optimizacijske funkcije ob upoštevanju električnih razdalj, velikosti skupnosti, števila in povezanosti skupnosti [21]. Uporabili so matriko električnih razdalj, ki opiše vpliv pretoka delovne moči med vozlišči v omrežju glede na razliko faznega kota napetosti. Električna razdalja oceni inkrementalno spremembo faznih kotov, ki je rezultat inkrementalnega prirastka pretoka delovne moči med vozlišči. Električne razdalje se izračunajo na osnovi inverzne vozliščne admitančne matrike in se bistveno razlikujejo od topoloških razdalj v električnih omrežjih – števila vej, ki jih uporabimo za topološko pot med vozlišči. Algoritem K-means generira začetne množice rešitev in EA izboljša začetne rešitve z uporabo multiplikativne združitvene funkcije, ki zajema povezanost skupnosti vozlišč, velikosti skupnosti, število skupnosti in indeks povezanosti vozlišč znotraj. 276 RIZMAN 6 ALGORITMI IZMENJAVE OZNAK Zelo učinkovit algoritem za odkrivanje skupnosti s skoraj linearno časovno zahtevnostjo je algoritem izmenjave oznak (LPA) [22]. Vsakemu vozlišču grafa dodeli enolično oznako, ki določa skupnost, v katero sodi vozlišče. Oznaka vsakega vozlišča se nato zamenja z oznako, ki jo ima večina sosedov. Iterativni proces se konča, ko ne pride do nobene zamenjave oznake. Vsa vozlišča z isto oznako pripadajo eni skupnosti. LPA uporablja matriko sosednosti. Uporabimo ga lahko tudi za električna omrežja. Za odkrivanje skupnosti v električnih omrežjih je bil predlagan algoritem LS [6]. Tradicionalna metoda širjenja vozlišč je posebna oblika algoritma LS. LPA v primerjavi z algoritmom odkrivanja skupnosti LS vsebuje manj lokalne informacije. Namesto matrike sosednosti, ki jo uporabi algoritem LPA, algoritem LS uporabi matriko podobnosti. Sprejem najpogostejše oznake sosedov zahteva dva izračuna v algoritmu LS. Najprej izračuna vsoto podobnosti med vozliščem in vsemi vozlišči skupnosti namesto izračuna vsote posameznih oznak sosednjih vozlišč v LPA. Ta vsota je podobnost med vozliščem in skupnostjo. Vozlišče privzame oznako skupnosti z največjo vsoto podobnosti, kar ustreza prejetju najbolj pogoste oznake v algoritmu LPA. Uporabljen je indeks podobnosti za merjenje bližine med različnimi vozlišči, ki ne upošteva električnih lastnosti. Osnovna ideja algoritma LS je, da se vsako vozlišče pridruži tisti skupnosti vozlišč, s katero ima največjo vrednost podobnosti, ki je vsota podobnosti vseh parov tega vozlišča in posameznega vozlišča skupnosti. Normaliziran indeks podobnosti opiše verjetnost, da vozlišče pripada skupnosti. Najpreprostejše merilo podobnosti med dvema vozliščema so skupni sosedi (enačba 3). 𝑝𝑜𝑑𝑜𝑏𝑛𝑜𝑠𝑡 𝑖𝑗 = 𝑁 (𝑖 ) ∩ 𝑁 (𝑗 ) (3) N(i) je množica sosedov vozlišča i in |N(i)| opiše število sosedov vozlišča i. Algoritem LS uporabi indeks podobnosti LS (enačba 4). 𝑝𝑜𝑑𝑜𝑏𝑛𝑜𝑠𝑡 = 𝐴 + 𝛽𝐴 2 + 𝛽 𝐴 3 (4) 𝛽 je parameter, ki ga prilagodimo za dobro prilagoditev odkrivanja gruč in A je matrika podobnosti. Indeks opiše število poti od vozlišča i do vozlišča j v treh korakih, ki indirektno opisuje povezave med sosedi vozlišča. Ta indeks opiše lokalne goste povezave podobno kot struktura skupnosti. Poskusi na primerjalnih omrežjih in električnih omrežjih kažejo učinkovitost algoritma LS. Algoritem odkrije tudi vozlišča, ki so mostovi med skupnostmi in jedri skupnosti. Predlagan algoritem lahko poleg odkrivanja skupnosti v električnih omrežjih prouči vlogo vozlišč mostov v kaskadnih napakah. 7 ZDRUŽITVENO HIERARHIČNO ODKRIVANJE SKUPNOSTI Združitveno hierarhično odkrivanje skupnosti je najpogostejša vrsta hierarhičnega združevanja, ki se uporablja za razvrščanje vozlišč v skupnosti na podlagi njihove podobnosti. Algoritem začne tako, da vsako vozlišče obravnava kot svojo skupnost. Nato se tisti pari skupnosti, ki najbolj povečajo optimizacijsko funkcijo, zaporedoma združijo. To algoritem ponavlja, dokler se vse skupnosti ne združijo v eno veliko skupnost, ki vsebuje vsa vozlišča. Rezultat je drevesna predstavitev vozlišč, ki jo imenujemo dendrogram. Hiter Newmanov algoritem [23] uporabi modularnost kot kriterijsko funkcijo in se je izkazal kot učinkovit za odkrivanje skupnosti tudi v električnem omrežju. Sodi v združitvene hierarhične algoritme odkrivanja skupnosti. Najslabši čas izvajanja algoritma je O((m + n)n) ali O(n 2 ) na redkih grafih. Newmanov hitri algoritem, opisan v viru [24], poišče funkcionalne skupnosti, in ne topoloških skupnosti v električnem omrežju kot preostali algoritmi. Avtorji predlagajo funkcionalno strukturo skupnosti na osnovi razširjenega uteženega mrežnega modela, opisanega z razširjeno matriko, ki ovrednoti jakost električne sklopljenosti (ECS). ECS odkrije funkcionalno strukturo skupnosti, ki deli omrežje na osnovi mrežne funkcionalnosti. Delitev električnega omrežja služi za ugotovitev, kateri deli omrežja so relativno neodvisni in samostojni v svoji funkcionalnosti. Običajna matrika sosednosti ovrednoti le topološko sosednost, ECS pa opiše električne značilnosti med poljubnima vozliščema v električnem omrežju. Razširjena matrika sosednosti EA vsebuje jakost električne sklopljenosti EAij za vsako povezavo med vozliščema i in j. Jakost sklopljenosti opiše funkcijsko lastnost prenosa med poljubnima vozliščema, če sta direktno ali posredno povezana. ECS opiše električne lastnosti omrežja med prenosom po električnem omrežju. Zmožnost prenosa med vozlišči je definirana s prenosno zmogljivostjo in enakovrednimi impedančnimi parametri. ECS med vozlišči i in j je Eij (enačba 5) [24]. 𝐸 𝑖𝑗 = 𝐶 𝑖𝑗 𝑍 𝑖𝑗 (5) ECS za vozlišče i opiše enačba 6. 𝐸 𝑖 = ∑ 𝐸 𝑖𝑗 (6) Tudi modularnost je definirana kot električna modularnost (enačba 7) [24]. 𝑄 𝑒 = 1 2𝑀 ∑ (𝐸 𝑖𝑗 − 𝐸 𝑖 𝐸 𝑗 2𝑀 ) 𝛿 (𝑖 ,𝑗 ) 𝑛 𝑖 ,𝑗 (7) ODKRIVANJA SKUPNOSTI V ELEKTRIČNIH OMREŽJIH 277 Newmanov hitri algoritem je razširjen z iskanjem največje električne modularnosti kot objektivne funkcije za odkrivanje funkcionalnih skupnosti v električnem omrežju. Newmanov hitri algoritem na začetku da vsako vozlišče v svojo skupnost. Električno modularnost Qe izračuna na osnovi matrike ECS. Ker razširjena matrika sosednosti EA ne opiše vozlišč, ki so direktno povezana, je treba za ugotavljanje direktnih povezav uporabiti še običajno matriko sosednosti A z elementi Aij. S pomočjo matrike A se najprej določijo direktne povezave med dvema skupnostnima. Dve skupnosti, ki imata vsaj eno direktno povezavo, se naključno združita v eno. Nato algoritem izračuna povečanje električne modularnosti ob združitvi skupnosti in ohrani združitev z največjim prirastom električne modularnosti. Algoritem združuje skupnosti, dokler ne dobi ene same. Največje število združitev je n-1, kjer je n število vozlišč. Rezultirajoča delitev je združitev z največjo modularnostjo. 8 DELITVENO HIERARHIČNO ODKRIVANJE SKUPNOSTI Najbolj priljubljen delitveni hierarhični algoritem je Girvan-Newmanov algoritem [25], ki robove med vozlišči izbriše glede na vrednost predlagane osrednosti vmesnosti. Osrednost vmesnosti je za vsako vozliče število najkrajših poti, ki gredo skozenj. Iz grafa izbriše rob z največjo vrednostjo osrednosti vmesnosti. Nato je treba ponovno izračunati vrednosti osrednosti vmesnosti. Po nekaj iteracijah dobimo iz povezanega grafa med seboj nepovezane skupnosti. Tiste povezave, ki imajo vrednost merila osrednosti vmesnosti največjo, so povezave med skupnostmi. Osrednost vmesnosti za celoten graf algoritem izračuna v času O(m n 2 ) in O(n 3 ) za redke grafe. Za vsak par točk v povezanem grafu obstaja vsaj ena najkrajša pot med oglišči, tako da je bodisi število robov, skozi katere poteka pot (za neutežene grafe), bodisi vsota uteži robov (za utežene grafe) čim manjša. Predlagane so bile mere osrednosti, ki temeljijo na funkcionalnosti. Takšno je merilo električne osrednosti [26], ki se razlikuje od topološke osrednosti. Dopolnjen Girvan-Newmanov algoritem je pogosto uporabljen, med drugim tudi za dinamično particijsko strategijo za obnovo elektroenergetskega sistema po izpadu [27]. Z uporabo lastnih vrednosti matrike elektroenergetskega omrežja prepoznava število podsistemov in nato z uporabo izboljšanega Girvan- Newmanovega algoritma razdeli izpadli sistem. 9 RAZPRAVA V prejšnjih poglavjih so opisane različne skupine algoritmov za odkrivanje skupnosti. Opredeljeni so klasični algoritmi odkrivanja skupnosti, ki so prilagojeni za odkrivanje skupnosti v elektroenergetskih sistemih. Algoritmi odkrivanja skupnosti so različno primerni in učinkoviti za delitve električnih omrežij. Spektralno gručenje je primerno za manjše podatkovne množice, ker ima zaradi uporabe spektra (lastnih vrednosti) matrike podobnosti za zmanjšanje dimenzionalnosti kompleksnost O(n 3 ). Genetski algoritmi so učinkoviti in uporabljeni za odkrivanje strukture skupnosti v mednarodnih prenosnih omrežjih. Delitvene metode gručenja uporabljamo za izboljšanje skupnosti, ki smo jih našli z drugimi metodami. Algoritmi za delitve grafov zahtevajo vnos števila skupnosti in v nekaterih primerih celo njihove velikosti, kar oteži njihovo uporabo in omeji uporabo le na primere, ko želimo razdeliti omrežje na določeno število delov. Hibridne metode delitvenih in genetskih algoritmov so se izkazale kot učinkovite. Delitveni algoritem (npr. K- means) generira začetne množice rešitev in EA izboljša začetno rešitev. Algoritmi izmenjave oznak so hitri, ne dajo pa enoličnih rešitev, in so torej primerni za hitro odkrivanje različnih skupnosti gruč. Delitveno hierarhično odkrivanje skupnosti in predvsem dopolnjen Girvan-Newmanov algoritem se pogosto uporabita v elektroenergetskih sistemih, kot na primer za dinamično particijsko strategijo za obnovo elektroenergetskega sistema po izpadu. 10 ZAKLJUČEK V tem prispevku razpravljamo o algoritmih in prilagoditvah za iskanje skupnosti v električnih omrežjih. Opišemo spektralne algoritme, delitvene algoritme, genetske algoritme, hibridne metode, algoritme izmenjave oznak za odkrivanje skupnosti ter združitveno in delitveno hierarhično iskanje skupnosti. Upamo, da bodo koncepti, prikazani v tem prispevku za odkrivanje skupnosti v realnih električnih omrežjih, pomagali proučiti bolj natančno delitev električnih omrežij v prihodnosti. LITERATURA [1] J. Li, C.-C. Liu, and K. P. Schneider, ''Controlled partitioning of a power network considering real and reactive power balance,'' IEEE Trans. Smart Grid, vol. 1, no. 3, pp. 261–269, 2010. [2] S. Fortunato, ''Community detection in graphs, '' Physics Reports- Review Section of Physics Letters, 486 ( 3-5), str. 75–174, 2010. [3] F. D. Zarandi, and M. K. Rafsanjani, ''Community detection in complex networks using structural similarity,'' Physica a-Statistical Mechanics and Its Applications, 503, str. 882–891, 2018. [4] S. Pahwa, M. Youssef, P. Schumm, C. Scoglio, and N. Schulz, ''Optimal intentional islanding to enhance the robustness of power grid networks, '' Physica a-Statistical Mechanics and Its Applications, 392 (17), str. 3741–3754, 2013. [5] G. A. Pagani, and M. Aiello, ''The Power Grid as a complex network: A survey, '' Physica a-Statistical Mechanics and Its Applications, 392 (11), str. 2688–2700, 2013. 278 RIZMAN [6] Z. Chen, Z. Xie, and Q. Zhang, ''Community detection based on local topological information and its application in power grid,'' Neurocomputing, 170, str. 384–392, 2015. [7] A.K. Kamwa, G. Pradhan, G. Joos, S. Samantaray, ''Fuzzy partitioning of a realpower system for dynamic vulnerability assessment'', IEEE Trans. Power Syst.24 (3) (2009) str. 1356– 1365. [8] J. J. López, J. A. Aguado, F. Martín, F. Munoz, A. Rodríguez, J. E. Ruiz, ''Hopfield-k-means clustering algorithm: a proposal for the segmentation of electricitycustomers'', Electr. Power Syst. Res. 81 (2) str. 716–724, 2015. [9] R. J. Sanchez-Garcia, M. Fennelly, S. Norris, N. Wright, G. Niblo, J. Brodzki, J. W. Bialek, ''Hierarchical spectral clustering of power grids'', IEEE Trans. Power Syst. 29 (5) str. 2229–2237, 2014. [10] J. Quirós-Tortós, P. Wall, L. Ding, V. Terzija, ''Determination of sectionalisingstrategies for parallel power system restoration: a spectral clustering-basedmethodology'', Electr. Power Syst. Res. 116 381–390, 2014. [11] R. J. Sánchez-García, M. Fennelly, S. Norris, N. Wright, G. Niblo, J. Brodzki, and J. W. Bialek, ''Hierarchical spectral clustering of power grids,'' IEEE Trans. Power Syst., 29 (5), str. 2229–2237, 2014. [12] J. B. MacQueen, in Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, edited by L. M. L. Cam and J. Neyman (University of CaliforniaPress, Berkeley, USA), v1, str. 281–297, 1967. [13] M. Guerrero, F. G. Montoya, R. Baños, A. Alcayde, and C. Gil, ''Community detection in national-scale high voltage transmission networks using genetic algorithms,'' Adv. Eng. Inform., 38, str. 232–241, 2018. [14] M. Guerrero, F. G. Montoya, R. Baños, A. Alcayde, and C. Gil, ''Adaptive community detection in complex networks using genetic algorithms,'' Neurocomputing, 266, str. 101–113, 2017. [15] J. H. Holland, ''Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence'', U Michigan Press, 1975. [16] R. Shang, J. Bai, L. Jiao, C. Jinm, ''Community detection based on modularity and an improved genetic algorithm'', Physica A 392, str. 1215–1231, 2013. [17] S. Kirkpatrick, M. Vecchi, et al., ''Optimization by simulated annealing'', Science 220), str. 671–680, 1983. [18] M. Guerrero, F. G. Montoya, R. Baños, A. Alcayde, C. Gil, ''Adaptive community detection in complex networks using genetic algorithms '', Neurocomputing 266, str. 101–113, 2018. [19] ME Newman, M. Girvan, ''Finding and evaluating comm.unity structure in networks''. Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113. doi: 10.1103/PhysRevE.69.026113. Epub 2004 Feb 26. PMID: 14995526. [20] Kernighan, B. W., and S. Lin, Bell System Tech. J. 49, 291, 1970. [21] E. Cotilla-Sanchez, P. D. Hines, C. Barrows, S. Blumsack, and M. Patel, ''Multi-attribute partitioning of power networks based on electrical distance,'' IEEE Trans. Power Syst., 28(4), str. 4979– 4987, 2013. [22] U. N. Raghavan, R. Albert, S. Kumara, ''Near linear time algorithm to detect community structures in large-scale networks'', Phys.Rev. E 76 (3) (2007) 036106. [23] M. E. Newman, ''Fast algorithm for detecting community structure in networks,'' Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., 69( 6) 2004, Art. no. 066133. [24] C. Zhao, J. Zhao, C. Wu, X. Wang, F. Xue, S. Lu, Power Grid ''Partitioning Based on Functional Community Structure.'' IEEE Access. str. 1–1. 10.1109/ACCESS.2019.2948606, 2019. [25] Girvan, M., and M. E. J. Newman, Proc. Natl. Acad.Sci. USA 99(12), 7821, 2002. [26] Z. Wang, A. Scaglione and R. J. Thomas, "Electrical centrality measures for electric power grid vulnerability analysis," 49th IEEE Conference on Decision and Control (CDC),str. 5792-5797, 2010. doi: 10.1109/CDC.2010.5717964. [27] C. Liu, Y.Xie, Y. Shi, K. Xu, Xie, M.Yin, "Dynamic Partition Strategy for Fast Restoration of Power System with Fast Cut Back Units ". Dianli Xitong Zidonghua/Automation of Electric Power Systems. 41, str.46–53, 2010.. 10.7500/AEPS20170204004. Krista Rizman Žalik je leta 1987 diplomirala, leta 1990 magistrirala in leta 1993 doktorirala na Tehniški fakulteti Univerze v Mariboru. Je izredna profesorica na Univerzi v Mariboru. Njena raziskovalna zanimanja vključujejo iskanje znanja v podatkih, podatkovno rudarjenje, gručenje in odkrivanje skupnosti v omrežjih.