# Algoritmoen konparaketa
## Laburpena
## I. Sarrera

Lan honen helburua Community Detection problema ebaztea da, hau da, elkarlan komunitate desberdinak detektatzea. Ebazten hasi aurretik, komunitate bat zer den jakin behar da. Komunitateak, kluster edo modulu ere deitzen direnak, erpinak dituzten multzoak dira, grafo batean propietate komunak partekatu edo antzeko rolak jokatzen dituztenak. Izan ere, komunitateak aspalditik aztertu izan dira eta gaur egun sareko sistema askotan aurki daitezke, biologian, informatikan, ingeniaritzan, ekonomian eta politikan adibidez [1].

Komunitate hauek “sare” bezala adierazten dira, eta sare hauetako bakoitza nodo edo erpin multzo baten bidez. Komunitate hauen arteko konexioak berriz, link edo ertzen bidez adierazten dira (ikus. 1.irudia). Grafoak klusterretan banatzearen arazoak intuitiboa dirudien arren, ez dago ondo definituta, ambiguoa izan daiteke, eta arazoa konpontzeko bidezko modu bat baina gehiago egon.

***1.irudia.** Hiru komutitateko grafo sinple bat. [2]*

Beraz, Community Detection problema grafoko moduluak eta antolakuntza hierarkikoa identifikatzean datza, grafoko topologiaren informazioa erabiliz. Grafoko banaketa ona dela neurtzeko, modularitatea erabil daiteke, komunitateen baten barruan ertz asko baina beste komunitateekiko gutxi daudela egiaztatzeko.

Lanaren antolakuntza honakoa da: II. sekzioan optimizazio problemaren nondik norakoak azaltzen dira, NIPSeko elkarlan grafoa aurkeztu eta modularitatean sakonduz. Ondoren, III. eta IV. sekzioetan problema ebazteko erabilitako bi algoritmoak azaltzen dira, tabu bilaketa eta inurrietan oinarritutako geruza bakarreko algoritmoa hain zuzen ere. Bi atal hauetan algoritmoen historia, funtzionamendua, eta gure problemarako izan dute egokitzapena aipatzen dira. V. sekzioan bi algoritmoekin egindako esperimentazioaren emaitzak azaltzen dira, parametroen aukeraketatik hasita, algoritmoen portaera azaltzen duten irudi, taula, analisi estatistikoarekin. Bukatzeko, VI. atalean lan honen inguruan ateratako ondorioak azaltzen dira.

## II. Optimizazio problema

Community Detection problemako kasu honetan, NIPS (Neural Information Processing Systems) kongresuan publikatu duten autoreen komunitateak aztertzen dira, 2014 eta 2015 urteen bitartean eman diren elkarlan komunitateak zehazki. Horretarako, elkarlan grafoa eraikitzen da eta komunitate kopuru maximoa ezarri. Beraz, kodetutako algoritmoak erabiliz, komunitate bakoitzean dauden autoreak (nodoak) zein diren jakin beharko da.

Bilaketa espazioaren inguruan, komunitate kopurua $x$ izanik, 0tik $x$ arteko zenbakiak erabiliko dira komunitateak adierazteko. NIPS grafoan 1843 autore daudenez, soluzioak errepresentatzeko 1843 tamainako bektore bat erabiliko da, eta posizio bakoitzeko elementuak dagokion autorearen komunitatea adieraziko du.

Proiektu honetan modularitatea erabiliko da kriterio bezala, helburu funtzioa inplementatzeko. Modularitateak komunitateen zatiketa egokia den neurtzen du, hau da, komunitateen barruan ertz asko daudela ziurtatzen du, beste komunitateekiko gutxi dauden bitartean.

Alde batetik, komunitate batean dagoen ertzen zatia (komunitate berean dauden erpinak elkartzen dituena) honakoa da:

$$\dfrac{1}{2m}\sum\limits_{vw} A_{vw} \delta (c_v,c_w)$$

$\delta$ funtzioa $\delta(i,j) = 1$ izanik $i=j$ gertatzen bada eta $0$ kontrako kasuan. Grafoko ertz kopurua adierazteko aldiz, $m = \frac{1}{2}\sum\limits_{vw} A_{vw}$ erabiltzen da. Sareko zatiketa ona bada, kopuru hau handia izango da, eta komunitate barruan ertz asko daudela adieraziko du. Hala ere, ez da komunitatearen egitura neurtzeko esanguratsua. Izan ere, erpin guztiak komunitate bakarrekoak balira, ekuazioak bere baliorik altuena, $1$, hartuko luke.

Beste alde batetik, $v$ erpin baten gradua, $k_v$, honela definitzen da:

$$k_v = \sum\limits_{w} A_{vw}$$

Bukatzeko, $v$ eta $w$ erpinen artean ertz bat existitzeko probabilitatea $\dfrac{k_v k_w} {2m}$ da. Beraz, hona hemen modularitatearen ($Q$) ekuazioa:

$$Q = \dfrac{1}{2m}\sum\limits_{vw}\left[ A_{vw}- \dfrac{k_{v}k_{w}}{2m} \right] \delta (c_v,c_w)$$

Behin modularitatearen ekuazioa azalduta, inplementazioko sasikodea honakoa izango litzateke:

_**Input**: G grafoa eta partizioa partizio posiblea_
_**Output**: modularitatea_

    # Matrizearen alde baterako
    for i = 0 to erpin_kopurua
        for j = i+1 to erpin_kopurua
            if partizio_bera() do
	        ertza_egoteko_probabilitatea_kalutatu()
                batura_eguneratu()
    batura = batura * 2

    # Matrizearen diagonal nagusirako
    for i = 0 to erpin_kopurua
            ertza_egoteko_probabilitatea_kalutatu()
	    batura_eguneratu()

    modularitatea = batura/(2*ertz_kopurua)

Aipatzekoa da, sasikode hau bi zatitan dagoela banatuta, matrizearen alde baterako zatian eta diagonal nagusirakoan. Izan ere, matrizea simetrikoa denez ez dago zertan aztertu matrizeko gelaxka guztiak. Ondorioz, ```batura = batura * 2``` egiten da matrizearen alde batekin lortutako baturarekin.

## III. Tabu Search
## IV. Inurrietan oinarritutako geruza bakarreko algoritmoa
## V. Esperimentazioa
### Parametroen aukeraketa
Parametro optimoenak zeintzuk diren jakiteko Grid Search teknika erabili dugu. Hau da, algoritmo bakoitzaren parametro espazioa bilaketa sakon baten bidez aztertu dugu parametro konbinaketa guztien artean hoberena zein den jakiteko.

Honela, Inurrietan oinarritutako geruza bakarreko algoritmoan bi parametro optimizatu ditugu: Grafoaren tamainarekiko inurrien populazioaren proportzioa eta algoritmoaren barnean erabiltzen den Simulated Annealing teknikako tenperatura aldaketa faktorea. Parametro bakoitzaren 10 balio posible aztertu dira, guztira 100 konbinazio izanik. Horietatik guztietatik, emaitzarik hoberenak ematen dituen parea $(0.889, 0.889)$ izan da $0.87$-ko _fitness_ balioa eman baitu.

Tabu Bilaketari dagokionez, aurrekoarekin egin dena ordez, ez dira 2 parametro optimizatu, bakarra baizik. Hain zuzen, mugimendu bakoitzean aztertuko diren auzokide kopurua. Parametro honen baliorik optimoena, $89$ dela egiaztatu da $0.694$-ko _fitness_ balioa eman baitu. Ordea, optimizazio hau bi pausokoa izan da, hau da, bi aldiz bilatu da parametro optimoena kasu honetan. Lehenengo aldian, parametroaren espazioa 10 zatitan banatu dugu eta horien artean parametro optimoena izango lukeen eremuan berriro bilaketa egin da era berean. Horrela, lehen bilaketan $[1, 205]$ eremua aukeratu da eta bigarrengoan, eremu horretan bertan, $89$ optimoena dela egiaztatu da.

### Diseinu esperimentala

## Bibliografia

[1] Santo Fortunato, Community detection in graphs, Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino,I-ITALY

[2] S.Fortunato, C.Castellano, Community structure in graphs, in:R.A.Meyers(Ed.), Encyclopedia of Complexity and Systems Science, vol.1, Springer, Berlin, Germany, 2009

[3] Clauset, A.; Newman, M. E. J. & Moore, C. Finding community structure in very large networks, Phyisical Review E 2004, 70, 066111

---

# Community Detection problema ebazteko bi algoritmo

Heuristikoetan gehien erabilitako metodoetako bat Bilaketa Lokala (Local Search) da. Metodo hau, bilaketa iteratiboko prozedura da, hasierako soluzio batetik hasita progresiboki hobetzen doana aldaketa edo mugimendu lokalak aplikatuz. Beraz, iterazio bakoitzean soluzioari mugimendu bat eragiten zaio, eta optimo lokal bat bilatu ondoren bukatzen du bilaketa. Askotan, optimo lokal hau ez da oso zehatza, eta algoritmoak konputazio denbora altua izan dezake soluzioari eragindako aldaketak ez badira kalitate onekoak.

Kasu honetan, Local Search-aren bi hedapen desberdin erabili dira arazo honi aurre egiteko: Tabu Bilaketa (Tabu Search) eta Inurrien Kolonien Optimizazioan (Ant Colony Optimization) oinarritutako SABA algoritmoa. Hurbilketa hauek bilaketa lokalaren pausuak jarraitzen dituzte, baina optimo lokala gainditzen lagun dezakete, aurrerago azalduko den bezala ([1]-ko 2.kapitulua).

## Tabu Search

### Historia
Tabu Search terminoa Fred Gloverrek (1986) ekarri zuen "meta-heuristika" terminoarekin batera. 80ko harmarkada bukaeran eta 90eko hamarkada hasierako hainbat artikulutan bilaketaren oinarrizko printzipioak zehaztu ziren, eta 1997. urtean argitaratutako "Tabu Search" liburuan bildu ziren. Metodo honek arrakasta handia izan zuen optimizazio problemetan, mundu errealeko aplikaziotan oinarritzen direnetan batez ere.

Tabu Bilaketa prozedura klasikoetan oztopo diren bideragarritasun edo optimotasun lokala gainditzeko metodoetan oinarritzen da. Horrela, kontuan hartzen ez diren edo "debekatuta" dauden zonaldeak aztertzeko aukera ematen du, murrizketak inposatu edo ezabatuz [1].

Prozedura honen ezaugarri bereizgarri bat egokitzen den memoriaren erabilera da, memoria gabeko edo herentzian oinarritutako memoria ahula erabiltzen duten metodoetan ez bezala. Honek, algoritmoaren exekuzioa kontrolatzen du debekatuak edo "tabu" diren mugimenduak gordez. Gainera, memoriaren bitartez problemaren ebazpeneko pausuak gordetzeaz gain, informazioa biltegiratzeko egituren beharra sortzen du.

### Funtzionamendua
Tabu Bilaketaren funtzionamendu orokorra ulertzeko, beharrezkoa da hurrengo kontzeptuak ezagutzea: Alde batetik, tabu lista dago, optimo lokaletik urruntzean zikloak ekiditeko erabiltzen dena. Hau gertatzen denean, metodo bat behar da bilaketak atzerako pausorik emango ez duela ziurtatzeko. Horretarako, mugimendu bat tabu dela erabakitzean (tabu listara gehitzean) egindako mugimenduekin sortutako eragina alderantzikatzea ekiditen da.

Tabu mugimenduak epe motzeko memorian gordetzen dira informazio kopuru jakin batekin. Kopuru honek mugimendu bat tabu izango den iterazioak mugatuko ditu, eta estatikoa nahiz dinamikoa izan daiteke (ikus. 2.5 [2]-n). Hala ere, mugimendu bat tabu izan arren, gerta daiteke bere balioa (helburu funtzioak emandakoa) aurkitu den guztiak baina hobea izatea. Mugimendua onar daiteke, Aspiration Criteria onartzen badugu, kasu honetan soluzioa aurkitutako guztietatik onena izatea, tabu izan arren. Irizpide honek baldintza ezberdinak izan ditzake, eta algoritmo bakoitzera egokitu.

Aspiration Criteriaz gain, beharrezkoa da Termination Criteria bat ere izatea. Teorian, bilaketa infinitua izan daiteke, problemako balio optimoa ezagutzen ez bada. Praktikan, bilaketa punturen batean bukatu behar da, irizpide ezberdinen arabera (iterazio kopuru maximo bat arte, iterazio batetik aurrera helburu funtzioaren balioa hobetzen ez den arte, balioak atalase bat gainditu arte...).

Beste alde batetik, Tabu Bilaketan areagotzea eta dibertsifikazioa aplika daitezke. Areagotzea epe erdiko memorian oinarritzen da, eta lortu diren soluzio onenetako "atributu onak" gordetzean datza, bilaketa zonalde ezberdinetan ere egiteko. Dibertsifikazioa Bilaketa Lokalean gertatzen den ohiko arazo bat ekiditeko erabiltzen da: bilaketa espazioko zati mugatu bat baino ez da aztertzen, eta soluzio onak lor daitezkeen arren, interesgarriak diren beste batzuk alde batera uzten dira. Beraz, epe luzeko memoria erabiltzen da, gutxien erabili diren atributuak ere aztertzeko.

### Gure problemara egokitzapena
Community Detection problemara itzuliz, modularitatea maximizatzeko algoritmoa egokitu da. Bilaketa espazioari dagokionez, ausazko ikuspuntu bat erabili da, soluzio batetik abiatuta ausazko mugimendu kopuru jakin bat sortuz. Kopuru hau algoritmoko parametro bat izango da, tamaina ezberdinekin probak egin ahal izateko. Tabu listaren tamainari dagokionez, luzera estatikoa erabili da, $t=sqrt(n)$ motakoa, non $n$ problemaren dimentsioa den, 1843 nodo hain zuzen ere.

Aspiration Criteriaren helburua, mugimendu bat tabu izan arren, aurkitu den soluzio onena bada kontuan hartzea izango da. Gainera, Termination Criteria iterazio kopuru bat betetzea izango da, hau ere programako parametro bat izanik. Ez da areagotze ez dibertsifikazio metodorik erabili, hau da, epe motzeko memoria soilik erabili da.

### Fluxu diagrama
Hona hemen problemara egokitutako algoritmoaren fluxu diagrama:


## Inurrietan oinarritutako geruza bakarreko algoritmoa (SABA)

Algoritmo hau Inurrien Kolonien Optimizazioan (Ant Colony Optimization) dago oinarrituta, hau da, inurriak kolonia batean duten portaeraz baliatuz egindako algoritmoen multzokoa da hau.

### Historia
Algoritmoak diseinatzeko metodo hau ez da berria, izan ere, inurrien portaeraz baliatzen ziren lehen inplementazioak 1989 agertu ziren [3]. Urte horretatik aurrera, antzeko algoritmo gehiago hasi ziren sortzen, batik bat, Gambardella eta Dorigo zientzialariek Inurrien Kolonien Sistema sortu zuten 1996ean [4] eta 2000. urtean lehen MAX-MIN Inurrien Sistema agertu zen Hoos eta Stützleren eskutik [5].

Gure algoritmo honi (SABA) dagokionez, esan liteke, 1997ean Gambardella eta Dorigo zientzialariek sortutako sistema dela interesgarriena lehenengo aldiz Bilaketa Lokal batekin nahastutako Inurrien Kolonien Sistema bat argitaratzen dutelako [6]. Algoritmo horretan Saltzailearen problema (TSP) ACO (Ant Colony Optimization) algoritmo baten bidez ebazten saiatzen dira Bilaketa Lokal batean oinarrituta. Algoritmo horretan eta honen arteko desberdintasuna da, esperimentu horren kasuan, inurri bakoitzak soluzio bat eraikitzen joaten da, ordea, algoritmo honetan inurri guztiak soluzio bakar bat optimizatzen saiatzen dira.

### Funtzionamendua
Atal honetan erabili dugun SABA algoritmoaren funtzionamendua azalduko da, baina hori mundu errealeko inurrien portaerarekin hobeto lotzeko, lehenik ACO algoritmo arrunten funtzionamendua nolakoa den azaldu beharra dago.

#### Inurriak Kolonietan nola funtzionatzen duten azalpena
Inurriek, izaki bizidun guztiek bezala, bizirauteko janaria behar dute, ondorioz, janariaren bila behar bezain beste distantziak bidaiatzen dituzte aurkitzen duten arte. Ordea, aurkitzen dutenean ez dute inolako modu zuzenik beraien koloniei janariaren kokapena partekatzeko, izan ere, inurriak kolonian bizi direnez, kolonia osoa asetuko duen janari kopurua behar dute eta horretarako jateko zerbait aurkitzen dutenean, ahal bezain beste inurri joan beharra daukate janariaren kokapenera ahal den guztia eskuratu ahal izateko. Baina, esan dugu ez dutela komunikatzeko bide zuzenik, orduan, nola lortzen dute beste inurriek janaria nun dagoen jakitea?

Inurriek gizakiontzat nahiko ohikoa den metodo bat erabiltzen dute janariaren bila joateko bidea erabakitzeko: Inurri gehienek egiten duten bidea hartzea erabakitzen dute kasu gehienetan. Ordea, hori ez da guztiz zuzena, inurriek ez dituzte inurrien kopuruetan oinarritutako erabakiak hartzen, inurriek uzten dituzten aztarna kopuruetan baizik. Izan ere, inurriak mugitzen direnean feronomonak uzten dituzte lurrean, honela, geroz eta inurri gehiagok zeharkatu bide bat, orduan eta feromona gehiago egongo dira bide horretan. Inurriak, orduan, feromona kopuruan oinarritzen dira erabaki bat hartu behar dutenean.

Baina, kontuz, feromonak denborarekin desagertu egiten dira. Horrek esan nahi du bide luzeek bide motzek baino feromona gutxiago dituztela. Adibidez, demagun inurri bat bide bat egiten hasten dela, jatorritik feromonak utziz, baina zoritxarrez inurri horrek ez du aurkitu janaririk eta itzultzen hasi beharra dauka feromonak desagertzen hasi baino lehen (bestela etxerako bidea galdu dezake). Kasu honetan gertatzen dena da, inurriak distantzia oso luzea egiten duela, baina denbora luzean itzultzen ez denez, utzitako feromonak ez dira nahikoa indartsuak beste inurri batek jarrai ditzan, gainera, pixkana desagertu egiten direnez, geroz eta beranduago itzuli, beste inurri batek bide hori hartzeko aukerak orduan eta gutxiago dira.

Kontrako kasuan, inurri batek janaria nahiko goiz aurkituko balu, oraindik feromona dexente dituen bidetik itzuliko litzateke, beti bezala, feromona gehiago utziz, hurrengo inurriren batek aukera handiagoa izateko bide hori aukeratzeko.

Metodo sinple hori erabilita, feromona kopurua bakarrik erabilita janaria non dagoen identifikatu dezakete inurriek.

Hala ere, hori ez da dena, demagun janari berberara iristeko bi bide sortu dituztela inurriek. Bata bestea baino luzeagoa da, ondorioz, motzak luzeak baino feromona gehiago izango ditu. Horrek inurri gehienek bide motzena aukeratzea eragingo du, ez hori bakarrik, gainera, inurriek bide motza hartzea nahiago dutenez, pixkanaka pixkanaka bide luzeko feromonen kopurua desagertzen joango da bide luzea hartzen duten inurrien kopurua zerora iritsi arte. Honela, inurriek biderik motzena edo optimoena aukeratzeko gai dira. Hori da Inurrien Kolonien Optimizazioan oinarritzen diren algoritmoak existitzeko arrazoia.

#### ACO metodo arrunten funtzionamendua
Inurrien Kolonien Sistemen erabilpen ohikoenak distantziekin lotutako problemek izaten dira, adibidez, aurretik aipatutako Saltzailearen Problema (TSP).

Problema hau saltzaile batek hiri batzuk zer ordenatan bisitatu beharko lituzkeen erabakitzean datza. Hau da, saltzailearen bide motzena aurkitzea litzateke helburua. Hori egiteko, inurri kopuru bat askatzen da hirien mapan, zehazki, grafoan. Inurri hauek hiri batetik beste batera mugitzen dira, bidean feromonak utziz eta bakoitzak soluzio bat sortuz. Feromonen balioak eredu edo matrize batean gordetzen dira eta inurriak mugitzen diren aldioro eguneratu egiten dira.

Honela, espezifikazioetan sartu gabe, bide motzena aurkitzea lortzen dute.

#### SABA bilaketa lokaleko algoritmoa
Aurreko ataletan azaldutako algoritmoak inurriek utzitako feromonetan daude oinarrituta. Ordea, SABA algoritmoak ez ditu feromonak erabiltzen, baina inurriak mugitzen dira grafoko nodoetatik.

Kasu honetan, inurri bakoitza grafoko nodo batean hasten da. Uneoro, inurri bakoitza nodo batetik beste batera igarotzen da jatorrizko nodoak dituen ertzez balioatuz. Ausaz aukeratzen du zein ertz gurutzatu. Gainera, hasieran, grafoko nodo bakoitza bere burua bakarrik duen komunitate batean dago, hau da, N nodo baleude, N komunitate egongo lirateke hasieran.

Algoritmo honen bereizitasuna da, inurri bat nodo batetik bestera igarotzean, nodo berria aurreko nodoaren komunitatera gehitzeko aukera ematen duela. Hain zuzen, hurrengo nodoa aurrekoaren komunitatean balegoko modularitatea kontrako kasukoa baino handiagoa balitz, hurrengo nodoaren komunitatea aldatuko litzateke, baina horrela ez balitz, probabilitate batekin ere aldatzeko aukera legoke (denbora guztian soluzio hoberena aukeratzen ez ibiltzeko, optimo lokaletan gelditzea eragotziz).

Honela, pixkanaka soluzioa eraikitzen joaten da komunitate kopurua gutxitzen delarik.

### Gure problemara egokitzapena
Gure problema Community Detection da, hau da, grafo batean komunitate optimoenak bilatzea da gure helburua. Ordea, Community Detection ohiko batean ez bezala, hasieatik komunitate kopurua definitu beharra daukagu eta komunitateak kopuru horrekiko bilatu. Gainera, helburu funtzio bezala grafoen modularitatea erabili behar dugu, algoritmoa horrekiko optimizatu ahal izateko.

#### Komunitate kopuru finkorako optimizatzen
Erabili dugun SABA algoritmoa, jatorriz, komunitate kopuru optimoa itzultzen du, ez dago aurredefinitu beharrik, izan ere, hasieran grafoko nodo bakoitza bere komunitate batean dago eta komunitate horiek batzen joaten dira kopurua jaitsiaraziz. Honela, kopuru optimora iristean algoritmoak ez du onartuko kopurua jaisten jarraitzea ez delako modularitatea hobetzen.

Ordea, kasu honetan hasieratik definitu beharra daukagu komunitate kopurua. Hori egiteko murriztapen bat jarri dugu algoritmoan:
Komunitate kopurua aurredefinitzen denean,
1. Lehen partizioa emandako komunitate kopuruarekin hasieratuko da.
2. Inurriak nodo batetik beste batera igarotzean, hurrengo nodoaren komunitatearen aldaketa komunitate kopurua aldatzen ez den bitartean onartuko da.

Bi horiek erabilita, hasieratik behar dugun komunitate kopurua definitzen da eta ondoren ez da onartzen kopuru hori aldatzen. Horrela, algoritmoa bukatzean komunutitate kopurua eskatzen zena izango da.

#### Bestelako aldaketak
Jatorrizko SABA algoritmoak, dagoeneko modularitatea erabiltzen zuen, baina gure kasuan ez bezala, LAR izeneko soluzioen adierazpen mota baterako dago prestatuta, ondorioz, algoritmo originala ahal den gutxien aldatzeko, soluzioak aipatutako adierazpen horrekin kudeatu dira, baina modularitatea kalkulatzerakoan, adierazpen horretatik gure modularitateak onartzen duenera bihurtzen dugu.

### Algoritmoaren sakonketa
$$P = e^{-\dfrac{f - f'}{T}}$$
$$Q = \dfrac{1}{2m}\sum\limits_{vw}\left[ A_{vw}- \dfrac{k_{v}k_{w}}{2m} \right] \delta (c_v,c_w)$$
$$f(v) = \sum\limits_{w}\left[ A_{vw}- \dfrac{k_{v}k_{w}}{2m} \right] \delta (c_v,c_w)$$

## Bibliografia

*[1] Michel Gendreau and Jean-Yves Potvin. 2010. Handbook of metaheuristics. Vol. 146. Springer.*

*[2] Búsqueda Tabu, 2003 Fred Glover / Belén Melián BÚSQUEDA TABÚ Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, año/vol. 7, número 019 Asociación Española para la Inteligencia Artificial Valencia, España*

*[3] M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson,An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989*

*[4] L.M. Gambardella and M. Dorigo, "Solving Symmetric and Asymmetric TSPs by Ant Colonies", Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, Nagoya, Japan, May 20-22, pp. 622-627, 1996;*

*[5] T. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889-914, 2000*

*[6] M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997*

------------------------------------------------

# Community Detection

_Jarraian datorren testua [1] artikuluan oinarrituta dago._

Proiektu honen helburua Community Detection problema ebaztea da, hau da, elkarlan komunitate desberdinak detektatzea. Kasu honetan, NIPS (Neural Information Processing Systems) kongresuan publikatu duten autoreen komunitateak aztertuko dira, 2014 eta 2015 urteen bitartean eman diren elkarlan komunitateak zehazki. Horretarako, elkarlan grafoa eraikiko da eta komunitate kopuru maximoa ezarri. Beraz, kodetutako algoritmoa erabiliz, komunitate bakoitzean dauden autoreak (nodoak) zein diren jakin beharko da.

Problema ebazten hasi aurretik, komunitate bat zer den jakin behar da. Komunitateak, kluster edo modulu ere deitzen direnak, erpinak dituzten multzoak dira, grafo batean propietate komunak partekatu edo antzeko rolak jokatzen dituztenak. Izan ere, komunitateak aspalditik aztertu izan dira eta gaur egun sareko sistema askotan aurki daitezke, biologian, informatikan, ingeniaritzan, ekonomian eta politikan adibidez.

Komunitateek aplikazio konkretuak izan ditzakete, adibidez, antzeko interesak dituzten bezeroen klusterrak identifikatzeak, produktuak gomendatzeko sistema eraginkorrak ezartzeko aukera eman dezake. Grafo handietako klusterrak datu egiturak sortzeko ere erabil daitezke, grafoetako datuak modu eraginkorrean biltegiratu eta nabigazio-kontsultak ahalbidetzeko.

Beraz, komunitate hauek “sare” bezala adierazten dira, eta sare hauetako bakoitza nodo edo erpin multzo baten bidez. Komunitate hauen arteko konexioak berriz, link edo ertzen bidez adierazten dira. Grafoak klusterretan banatzearen arazoak intuitiboa dirudien arren, ez dago ondo definituta. Adibidez, komunitate eta partizio kontzeptuak zorrotz definituak ez daudenez, ausazkotasun eta zentzu maila bat eskatzen du. Izan ere, anbiguotasuna dela eta, arazoa konpontzeko bidezko modu bat baina gehiago daude.

Beraz, Community Detection problema grafoko moduluak eta antolakuntza hierarkikoa identifikatzean datza, grafoko topologiaren informazioa erabiliz. Grafoko banaketa ona dela neurtzeko, modularitatea erabil daiteke, komunitateen baten barruan ertz asko baina beste komunitateekiko gutxi daudela egiaztatzeko.

Komunitateen detekzioa garrantzitsua da beste arrazoi batzuengatik ere. Moduluak eta haien mugak identifikatzeak, moduluen posizioen arabera erpinak sailkatzeko aukera ematen du. Beraz, multzoetan posizio zentrala duten erpinek (taldeko kideekin ertz asko partekatzen dituztenek) taldeko kontrol eta egonkortasunerako garrantzi handia izan dezake. Modulu ezberdinen arteko mugetan kokatuta dauden erpinek ere, bitartekaritza eginkizun garrantzitsua dute eta komunitate desberdinen arteko harremanak zuzentzen dituzte.

# Helburu-funtzioa

_Jarraian datorren testua [2] artikuluan oinarrituta dago._

Proiektu honetan modularitatea erabiliko da kriterio bezala, helburu funtzioa inplementatzeko. Modularitateak komunitateen zatiketa egokia den neurtzen du, hau da, komunitateen barruan ertz asko daudela ziurtatzen du, beste komunitateekiko gutxi dauden bitartean.

Alde batetik, komunitate batean dagoen ertzen zatia (komunitate berean dauden erpinak elkartzen dituena) honakoa da:

$$\dfrac{1}{2m}\sum\limits_{vw} A_{vw} \delta (c_v,c_w)$$

$\delta$ funtzioa $\delta(i,j) = 1$ izanik $i=j$ gertatzen bada eta $0$ kontrako kasuan. Grafoko ertz kopurua adierazteko aldiz, $m = \frac{1}{2}\sum\limits_{vw} A_{vw}$ erabiltzen da. Sareko zatiketa ona bada, kopuru hau handia izango da, eta komunitate barruan ertz asko daudela adieraziko du. Hala ere, ez da komunitatearen egitura neurtzeko esanguratsua. Izan ere, erpin guztiak komunitate bakarrekoak balira, ekuazioak bere baliorik altuena, $1$, hartuko luke.

Beste alde batetik, $v$ erpin baten gradua, $k_v$, honela definitzen da:

$$k_v = \sum\limits_{w} A_{vw}$$

Bukatzeko, $v$ eta $w$ erpinen artean ertz bat existitzeko probabilitatea $\dfrac{k_v k_w} {2m}$ da. Beraz, hona hemen modularitatearen ($Q$) ekuazioa:

$$Q = \dfrac{1}{2m}\sum\limits_{vw}\left[ A_{vw}- \dfrac{k_{v}k_{w}}{2m} \right] \delta (c_v,c_w)$$

Behin modularitatearen ekuazioa azalduta, inplementazioko sasikodea honakoa izango litzateke:

_**Input**: G grafoa eta partizioa partizio posiblea_

_**Output**: modularitatea_

    # Matrizearen alde baterako
    for i = 0 to erpin_kopurua
        v = erpina_lortu(i)
        for j = i+1 to erpin_kopurua
            w = erpina_lortu(j)
            if partizio_bera(v,w) do
	            ertza_egoteko_probabilitatea =
                    (gradua(v)*gradua(w)) / (2*ertz_kopurua)
                batura += ertza - ertza_egoteko_probabilitatea
    batura = batura * 2

    # Matrizearen diagonal nagusirako
    for i = 0 to erpin_kopurua
        v = erpina_lortu(i)
        ertza_egoteko_probabilitatea =
            (gradua(v)*gradua(v)) / (2*ertz_kopurua)
	    batura += ertza - ertza_egoteko_probabilitatea

    modularitatea = batura/(2*ertz_kopurua)

Aipatzekoa da, sasikode hau bi zatitan dagoela banatuta, matrizearen alde baterako zatian eta diagonal nagusirakoan. Izan ere, matrizea simetrikoa denez ez dago zertan aztertu matrizeko gelaxka guztiak. Ondorioz, ```batura = batura * 2``` egiten da matrizearen alde batekin lortutako baturarekin.

## Bibliografia

*[1] Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino,I-ITALY*

*[2] Clauset, A.; Newman, M. E. J. \& Moore, C. Finding community structure in very large networks, Phyisical Review E 2004, 70, 066111*