Hiukan verkkoa ja teoriaa

Verkkoteoria, mitä siihen nyt sanoisi. Hieno matematiikan haara, jolla pystyy visualisoimaan paljon mahtavia juttuja. Käyttämällä vaikka matriisirotaatiolineaarioptimointialgoritmiä ;)

Mihis muuhunkaan verkkoteoria istuisi paremmin, kuin sosiaalisiin verkostoihin? Lue: Facebookkiin. Tuo suuri ja paha Facebook, joka pitää kirjaa kavereistamme on loistava kohde.

Ideahan on yksinkertainen. Dumpataan Facebook:sta data ja piiretään sen avulla verkkokaavio. Ainut ongelma on vain, että alkuperäinen data ei ole siinä muodossa, että siitä saisi suoraan mitään järkevää aikaan. Tarvitaan siis jonkinlainen parseri väliin. Sellaistahan ei tietenkään valmiiksi löydy mistään. Joten semmonen tarvitsee tehdä.

Alunperin lähdin parseria toteuttamaan Node.js:llä ja sain sen pienten alkuongelmien jälkeen pelaamaan loistavasti. Jossain vaiheessa vain totesin, että blaah ja siiryin Pythoniin. Pitänee kyllä opetella node.js:sää tässä jossain vaiheessa paremmin.

Facebook tarjoaa suht mukavan Graph API:n jonka kanssa voi jutella Facebookin oman FQL kielen avulla. Muistuttaa hyvin paljon SQL:lää.

Esim. kaikkien omien kavereiden käyttäjä id:eet voi hakea.

SELECT uid2 FROM friend WHERE uid1 = <oma uid>

tai käyttäjän nimi id:n perusteella

SELECT name FROM user WHERE uid = <käyytäjän uid>

ja tarkistaa onko käyttäjät  A ja B kavereita keskenään

SELECT uid2 FROM friend WHERE uid1 = <A uid> AND uid2 = <B uid>

Jokainen kutsu tehdään HTTPS:n yli ja tiedot palautuu JSON-formaatissa, joka on oikein kiwi jatkokäsittelyä silmällä pitäen. Pullonkaulaksi muodostuu HTTPS-kutsut, joten homma kannattaa säikeistää. Sillä kaveruustarkistuksia saa tehdä aikas paljon. Koska jo esim. 150 kaverusta voidaan laittaa kättelemään 11175:llä eri tavalla.

Latex formula

Sadan kaverin lisäys nostattaa summa jo huomattavasti.

Latex formula

Kun kaikki on vihdoinkin saatu tarkistettua niin tiedot pitää pystyä ulostamaan myös sopivassa formaatissa. GEXF on tähän tarkoitukseen hyvin suoraviivainen. Listataan vain solmukohdat ja niiden väliset kytkökset.

Erittäin yksinkertainen esimerkki.

<gexf xmlns="http://www.gexf.net/1.2draft" version="1.2">
    <meta lastmodifieddate="2009-03-20">
        <creator>Gexf.net</creator>
        <description>A hello world! file</description>
    </meta>
    <graph mode="static" defaultedgetype="directed">
        <nodes>
            <node id="0" label="Hello" />
            <node id="1" label="Word" />
        </nodes>
        <edges>
            <edge id="0" source="0" target="1" />
        </edges>
     </graph>
</gexf>

Vielä pitäisi saada kaavio aikaseksi. Itse käytin avoinmen koodin Gephi:iä, joka on siis omien sanojensa mukaan “graph visualization and manipulation software”. Teemo Tebest on mm. kirjottanut asiasta blogissaan. Kannattaa muuten kattoa. Huitsin mielenkiintosta juttua. Oikeasti ammattilainen näyttää miten näitä kuuluu tehdä ;).

Hetken aikaa Gephiä pyöriteltyä sain jopa jotain aikaiseksi.

Kuvasta pystyy selvästi erottamaan eri kaveriporukat ja ns. supersolmut. Ts. ihmiset, jotka ovat kaikkien kavereita.

Kuten huomataan, niin aika pienestä määrästä ihmisiä sadaan tosi sotkuinen kuva. Pitäisi tälle jotain vielä kehittää. Irkissä tästä olikin puhetta, että mikä olisi viisain tapata asia esittää. Otto mm. ehdotti tämmöistä. Ongelmaksi tulee vaan, jos useampi “supersolmu” haluaa olla samojen ihmisten kanssa ystäviä. Kuitenkin jost tästä lähtis pohtimaan ja jalostamaan ideaa. Katsoo nyt mitä lopulta keksii.

This entry was posted in Höpinät, Jotain aivan muuta and tagged , , , , , , , . Bookmark the permalink.

3 Responses to Hiukan verkkoa ja teoriaa

  1. Pingback: Lisää verkkoa | Sounds like a plan

  2. Teemo Tebest says:

    Hei,

    kiva nähdä, että tekijöitä riittää muitakin eikä tässä toinen toistaan ammattilaisempia olla :)

    Huomasitko muuten, että FQL-kielessä pystyi niputtamaan noiden kaveruussuhteiden kyselyn niin, että on mahdollista kysyä kerralla keiden näistä esim. 300:sta käyttäjästä kanssa kaveri tämä henkilö x on. Eli joudut tekemään Facebook FQL-kyselyn vain yhtä monta kertaa kuin datassasi on käyttäjiä.

    Esimerkki FQL-kysely menee siis jota kuinkin näin:
    “SELECT uid2 FROM friend WHERE uid1 = %s and (%s)” % (uid1, query)

    missä muuttuja query on OR-ehdolla eroteltu lista uid-arvoja.

    _teemo_

Leave a Reply

Your email address will not be published. Required fields are marked *