|
[[File:6n-graf.svg|thumb|250px|Suuntaamaton verkko]]
{{Korjattava|Esseemäinen, lyhennettävä}}
{{tarkistettava|artikkelin sisällöllä ei ole juuri mitään tekemistä määritelmässä mainitun matematiikan verkkoteorian kanssa}}
'''Verkkoteoria''' eli '''graafiteoria''' on [[matematiikka|matematiikan]] osa-alue, joka tutkii kohteiden välisten suhteiden esittämiseen käytettäviä matemaattisia malleja eli [[verkko|verkkoja]]<ref>Nystuen, J. D., & Dacey, M. F. (1961). A graph theory interpretation of nodal regions. Papers in Regional Science, 7(1), 29-42.</ref>. VerkkojaVerkot koostuvat solmuista ja niitä yhdistävistä kaarista, jotka voivat olla suunnattuja tai suuntaamattomia. Verkkoteoriaa voidaan käyttääsoveltaa erilaistenmonilla suhteideneri jatieteenaloilla<ref>Gross, prosessienJ. mallintamiseenL., niin& fysikaalisissaYellen, J. (2005). Graph theory and its applications. CRC press.</ref>, kuten fysiikassa<ref>Gutman, I. & Trinajstić, N. (1972) Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons, Chemical Physics Letters, Vol. 17, No. 4</ref>, biologisissabiologiassa<ref>Mason, O. & Verwoerd, M. (2007) Graph theory and networks in Biology, IET Systems Biology, Vol. 1, No. 2</ref>, sosiaalisissasosiologiassa<ref>Harary, F., & Norman, R. Z. (1953). Graph theory as a mathematical model in social science. Ann Arbor: University of Michigan, Institute for Social Research.</ref><ref>Barnes, J. A. (1969). Graph theory and social networks: A technical comment on connectedness and connectivity. Sociology, 3(2), 215-232.</ref> kuin tietoteknisissäkin<ref>Hayes, B. (2000) Computing Science: Graph Theory in Practice: Part I, American Scientist, Vol. 88, No. 1</ref> systeemeissä. Verkkoteoriaa voidaankin soveltaa monilla eri tieteenaloilla<ref>Gross, J. L., & Yellen, J. (2005). Graph theory and its applications. CRC press.</ref>.
Suomessa tästä matematiikan haarasta käytetään yliopistosta riippuen kahta eri nimitystä eli verkko- tai [[graafiteoria]]{{Kenen mukaan}}. Myös käsitteiden nimikirjo poikkeaa opetuspaikan mukaan. Samoin verkkoteoriasta on erotettava omana alueenaan vielä [[verkostotiede|verkostojen teoria]]. Pohjimmiltaan verkko on verkkoteorian määrittämä solmujen eli pisteiden ja niitä yhdistävien välien eli kaarien kokonaisuus. Topologisessa verkkoteoriassa myös välien erottamat alueet huomioidaan. ''[[Verkko]]'' kuvaa verkkomaisen rakenteen riippumatta sen sisällöstä ja tulkinnasta ja esittää, mitä reittejä verkossa eri pisteiden välillä on. Verkkoja on myös lähes kaikkialla luonnossa ja ihmisen toiminnassa. Verkkoteoria on täten osa olemassaolon yleisempää ymmärtämistä.
==Verkkoteorian alku: Euler, Erdős ja Renyi==
Verkkoteorian alkuna pidetään sitä, kun [[Leonhardt Euler]] ratkaisi [[Königsbergin siltaongelma]]n vuonna [[1736]]. Seuraava tärkeä etappi oli Königin tasan 200 vuotta myöhemmin vuonna [[1936]] julkaisema ensimmäinen verkkoteoriaa kattavasti käsittelevä kirja. Tärkeä verkkoteorian perusteos on myös [[Frank Harary]]n vuonna 1968 julkaisema ''Graph Theory''. Verkkoteoriasta on kehittynyt myös verkostoteoria, jonka esittelivät [[Paul Erdős]] ja [[Alfred Renyi]] vuonna 1959 ja joka perustui satunnaiseen verkkoon. Siinä oleellista olivat topologia, staattisuus ja satunnaisuus. Sen mukaan verkko oli valmiiksi olemassa ja yhteydet ja solmut olivat satunnaisia. Tästä seurasi muun muassa se, että solmujen yhteysmäärät olivat tilastollisesti jakautuneita. Verkosta löytyi muun muassa tyypillinen solmu.
Erdos ja Renyi törmäsivät todellisten verkkojen hämmentävään kompleksisuuteen ja olettivat, että verkot ovat satunnaisia. Satunnaisten verkkojen yhteysmäärät per solmu ovat lähes samat. Yhteyksien määrä noudattaa [[Poissonin jakauma]]a, jossa suurella määrällä solmuja on sama määrä yhteyksiä.
Satunnaisten verkkojen teoria perustui ensin siihen, että solmut olivat jo valmiiksi olemassa. Verkottuminen ei alkanut jostain eikä kehittynyt. Toiseksi solmut olivat samanarvoisia. Kumpikaan näistä oletuksista ei pidä paikkaansa todellisissa verkoissa. Kasvusta seuraa, että ensimmäiset solmut ehtivät kerätä eniten yhteyksiä (ajan neliöjuuren mukaan). Muodostuu kytkijöitä (hubs).
==Skaalavapaa verkkoteoria==
'''Skaalavapaa verkkoteoria''' on uusi 2000-luvun alussa esitetty käsitys verkoista. Sen ydin on, että verkko syntyy jossakin vaiheessa ja verkko kasvaa. Verkko on siis [[evoluutio|evolutionäärinen]] ilmiö. Verkko on skaalavapaa, koska solmujen yhteysmäärät ovat jakautuneet eksponentiaalisesti, verkossa löytyy paljon pienen yhteysmäärän solmuja, mutta myös hyvin suuren yhteysmäärän solmuja. Monet luonnon verkot ovat skaalavapaita.
Uuden skaalavapaan teorian sovellutuksia löytyi matematiikasta, fysiikasta, sosiologiasta, taloustieteestä, biologiasta, epidemiologiasta, kielitieteestä, tieteellisestä kirjoittamisesta, sodankäynnistä, terrorismista, ym.
===Skaalavapaa verkko ja tieteen paradigma===
Skaalavapaa verkkoteoria on hyvä esimerkki tieteen kehittymisestä, uuden [[paradigma]]n muodostumisesta. Jollakin hetkellä on olemassa yleisesti hyväksytty vallitseva paradigma. Sitten tulee uusia havaintoja, joita ei sillä pystytä selittämään. Vähitellen muodostuu uusi käsitys kyseisen tieteen teoriasta. Yleensä uusi teoria pystyy selittämään enemmän ilmiöitä ja paremmin.
Aiempi tiede, asian hajottaminen pienempiin osiinsa ja näiden pienempien osien ymmärtäminen on johtanut umpikujaan. Osoittautui, että kokonaisuuden rakentaminen osista voi tapahtua monella, lukemattomilla tavoilla, joista luonto käyttää vain muutamaa. Luonto siis kokeilee kaikkea ja valitsee elinkelpoisimmat. Tullaan ensin [[kompleksisuus|kompleksisuuden]] hallintaan, mahdollisesti seuraavien vuosisatojen tieteen pääteemaan. Toiseksi tullaan edellä mainitun kokeilemisen oleellisuuteen evoluutiossa. Periaate toimii jo muun muassa ohjelmistojen, algoritmien kehittämisessä, taloudessa (keiretsu), riskirahoituksessa (vain osa rahoitettavista yrityksistä onnistuu)...
===Skaalavapaan verkon ominaisuuksia===
Uuden verkostoteorian mukaan verkot elävät ja kehittyvät eivätkä solmut ole tasa-arvoisia. Niiden kehitystä ohjaa keskeisesti:
* kasvu
* houkuttelevuustekijä ja
* hubit, kytkijät (hubs), eli hyvin runsaiden yhteysmäärien solmut. Kytkijät ovat todellisten verkkojen avaintekijät.
Syntyy skaalavapaa malli. Sen solmujen yhteydet muodostava potenssi- (power) lain mukaisen jakautuman. Siinä ei ole tyypillistä solmua. Skaalavapaan mallin oleellisia ominaisuuksia ovat ensin siis kasvu ja houkuttelevuustekijä.
Skaalavapaassa mallissa on paljon vähän yhteyksien solmuja, useimmissa jonkun verran, mutta myös solmuja joissa hyvin paljon yhteyksiä. Potenssilain mukainen planeetta olisi seuraavanlainen: hyvin paljon todella pieniä asukkaita. 30 metrin asukkaat eivät kuitenkaan mahdottomia. 6 miljardin asukkaan planeetalla löytyy myös yksi vähintään 2600 metriä pitkä asukas.
Skaalavapaassa mallissa verkon topologian kuvaamisesta ollaan siirrytty sen mekanismin ymmärtämiseen, joka muodostaa verkon [[dynamiikka|dynamiikan]]. Muodostuu vastaparit:
* staattinen - kasvava
* satunnainen - skaalavapaa ja
* struktuuri - evoluutio
Todelliset verkot ovat hyvin yleisiä maailmassa, monella tieteenalalla. Verkkojen muodostuminen liittyy muodonmuutokseen.
===Klusterit ja heikot yhteydet===
Todelliset verkot sisältävät useimmiten seuraavan suurrakenteen: Ensin ovat olemassa pienen lähipiirin voimakkaat ja kaikkia koskevat liitynnät, aliverkko, [[klusteri]]. Sitten muodostuvat heikot yhteydet muihin klustereihin. Jo keskimäärin noin yhdellä yhteydellä per klusteri, aliverkot verkottuvat superverkoksi, joka alkaa elää omaa elämäänsä. [[Stuart Kauffman]]in tutkimuksissa kaksi keskimääräistä yhteyttä per solmu on hyvin tärkeä raja. Katso [[Evoluutio#Evoluutio ja olemassaolon systeemit|Evoluutio ja olemassaolon systeemit]]
Klustereiden sovellutuksia ovat:
* sosiologia (perhe, läheiset ystävät)
* talous ([[keiretsu]]-idea Japanin taloudessa)
* aivot (noin kaksi miljoonaa suuraluetta)
* biologia (läheiset solut kommunikoivat keskenään, DNA:n lisäksi olion kehityksen vaikuttaa paikallinen informaatio, solujen kemian yhteen sitoma verkko)
* fysiikka (jäätyminen, magneetin muodostuminen; ensin muodostuu useita atomeja käsittäviä, samalla tavalla "käyttäytyviä" atomiklustereita).
Klusterit ja niistä muodostuva superverkko on globaali/paikallinen- sovellutus. Klusterien ymmärtäminen on tärkeää monen ilmiön ymmärtämiseksi verrattuna yksittäisen toimijan ymmärtämiseen. Esimerkiksi atomiklusterit ovat aineen käyttäytymisessä tärkeämpiä kuin yksittäiset atomit.
[[Pareton periaate|80/20- sääntö]] liittyy usein klustereihin. Siis siihen, että toiminnassa on muutama avaintekijä, jotka vaikuttavat keskeisesti lopputulokseen. Keskittymällä avaintekijöihin, saadaan eniten tuloksia vähimmillä resursseilla.
Heikot yhteydet ovat erittäin tärkeitä, muun muassa työnsaannissa verrattuna vahvoihin klustereiden yhteyksiin. Johtajat saavat 70% enemmän uusista työpaikoista heikkojen lenkkien kautta kuin tuttavapiiristä (vahvat yhteydet). Klustereidemme tieto on samaa kuin meillä, ne eivät siis tuo meille uutta tietoa. Se tulee heikoista yhteyksistä. Edellä oleva on yksi sosiologian suurimpia tutkimustuloksia ja eniten siteerattuja.
===Kytkijät, supersolmut (hubs)===
Ihmisverkoissa löytyi yksilöitä, joilla oli paljon enemmän yhteyksiä, kuin satunnaisten verkkojen teoria salli. He olivat ympäristönsä supervaikuttajia, henkilöitä, jotka tunsivat kaikki ja jotka kaikki tunsivat. He luovat trendejä ja muotia. Kytkijöitä löytyy monelta alalta, muualtakin kuin ihmisyhteisöistä, muun muassa webissä kyseisen tyyppiset kytkimet ovat verkon avaimia.
Kytkijöitä ei pitäisi olla olemassa satunnaisten verkkojen teoriassa. Kytkijöiden houkuttelevuuteen katoaa webin näennäinen demokraattisuus: Kuka tahansa voi julkaista mitä tahansa kaikille webissä. Tämä pitää paikkansa. Sen sijaan se mitä luetaan on aivan eri asia. Webissä on oleellista, montako sisään tulevaa linkkiä dokumentilla on.
Kytkijät (hubs) esiintyvät useammissa suurissa monimutkaisissa verkoissa kuin mitä tiedemiehet ovat vielä pystyneet tutkimaan. Ne ovat kaikkialla läsnä olevia kompleksisen kytketyn maailman geneerisiä rakennuspalikoita. Ne luovat oman maailmansa ja lyhentävät kahden mielivaltaisen solmun etäisyyttä.
===”Voittaja vie kaiken”- periaate===
Kytkijät, supersolmut tarkoittavat käytännössä periaatetta: "Voittaja vei kaiken". Periaate on siis kehittyvien, dynaamisten verkkojen ominaisuus. Eräinä esimerkkejä olemassa olevassa olevasta tilanteesta hyötyjinä tietoliikeennetoimialalla voidaan pitään mm. yrityksia Intel, Microsoft, Google ja Nokia. Apple on viime aikoina tuotteillaan iPhone ja IPad toiminut oman toimialansa supersolmuna.
Googlessa haku antaa osumat viittausjärjestyksessä, eniten viitattu sivu ensin. Käytännössä tästä muodostuu "voittaja vie kaiken"- ilmiö. Jos sivu on tarpeeksi hyvin laadittu, kukaan ei hae esimerkiksi sivua 524, joka on yhtä hyvin laadittu tai parempikin. Ensimmäinen riittävän hyvin laadittu sivu saa jatkuvasti uusia viittauksia.
===Skaalavapaan verkkoteorian sovellutuksia===
Sodankäynnissä skaalavapaa verkkoteoria antaa pohjaa uudelle [[informaatiosodankäynti]]ä seuraavalle sodankäyntitavalle, [[verkostokeskeinen sodankäynti|verkostokeskeiselle sodankäynnille]] (engl. Network-Centric Warfare, NCW).
Verkko on sama kuin kokonaisuus. Tämä viittaa [[Heinz R. Pagels]]in esittämään tieteen mahdolliseen uuteen [[paradigma]]an, kompleksisuuden hallintaan.
Oikeat verkot ovat itseorganisoituvia. Suurista määristä koostuessaan, ne johtavat ilmiömäiseen [[emergenssi|emergenttiin]] käyttäytymiseen. Ne toimivat ilman keskeistä johtoa.
==Verkko ja kompleksisuus==
Verkko on hyvin kompleksinen rakenne. Verkkojen ymmärtäminen on siis merkittävä osa kompleksisuuden hallintaa. Seuraava suuri haaste, seuraavan vuosisadan haaste, on nimenomaan kompleksisuuden hallintaa. Tämä viittaa vahvasti fyysikko [[Heinz R. Pagels]]iin, jonka mukaan kompleksisuus on seuraavan 300 vuoden tieteen uusi teema.
==Graafialgoritmeja==
==Katso myös==
* [[Verkostotiede]]
* [[Heinz R. Pagels]]
* [[Skaalautumaton verkko]]
* {{kirjaviite | Tekijä=Barabási, Albert-László | Nimeke=Linkit: Verkostojen uusi teoria | Selite=(Linked: The new science of networks, 2002.) Suomentanut Kimmo Pietiläinen | Julkaisupaikka=Helsinki | Julkaisija=Terra cognita | Vuosi=2002 | Tunniste=ISBN 952-5202-66-6}}
*https://www.doria.fi/bitstream/handle/10024/2841/kolmival.pdf?sequence=1
=== Viitteet ===
{{Viitteet}}
== Kirjallisuutta ==
| 