visualisatie linked network

[Verwijderd]

Ik wil met behulp van JS een linked network weergeven, iets als dit:



Ik heb van elke node info met welke andere hij is gelinked, verder niets. Geen plaatscoordinaten dus. Wat ik graag wil is een algorithme die voor mij een zo lekker mogelijke verdeling maakt. Dit wil ik onder andere gebruiken voor het weergeven van moleculen (uit cml), maar ook voor algemenere netwerken (contact netwerk en een citatienetwerk). Probleem is dat ik niet goed uit een goede methode kom

ik heb al eens dit gemaakt: http://www.rikkertkoppes.com/brain2.0/network/springs.html waar gerekend wordt met veren tussen de verschillende nodes (voor Fx: http://www.rikkertkoppes.com/brain2.0/network/springs.php in svg)

Daar ben ik heel fysisch te werk gegaan, dus voor elke node de links langslopen, de afstand ertussen uitrekenen, vervolgens de kracht, dan alle krachten van alle links optellen, delen door de "massa" en de versnelling uitrekenen, daaruit volgt dan vervolgens een verplaatsing van 1 node.

Dat is erg omslachtig allemaal. Als ik nu voorstel dat alle nodes ladingen zijn en elkaar afstoten kom ik op het volgende:

bekijk voor elke node:
  de afstand tot alle andere nodes,
    als deze binnen een bepaalde straal zit (om niet alles te hoeven meenemen):
      verplaats beide nodes een stukje uit elkaar (evenredig met 1/r[sup]2[/sup])
  herhaal dit voor de afstand tot alle nodes
herhaal dit voor alle nodes

dat zou alle nodes uit elkaar drijven (tot de rand van het gebied als je dat erbij haalt). Iets netter zou zijn om eerst alle verplaatsingen uit te rekenen en dan op te tellen voor alle nodes en dan pas daadwerkelijk uit te voeren. Dat doe ik ook bij die veren.

Alleen nu nog de links ertussen. Natuurlijk worden twee nodes die aan elkaar gelinked zijn niet uit elkaar gedreven, da's een kwestie van checken, maar een andere node die een bepaalde node wegduwt, heeft zo ook invloed op alle nodes die aan die laatste gelinked zijn. Hoe ga ik dat oplossen?

[moozzuzz]

optelsom van de *krachten* op een node?

[André]

Dit idee heb ik eens eerder gezien, ik vind het wel een grappig iets om zo te visualiseren. Deze is bijvoorbeeld gemaakt voor websites:
http://www.aharef.info/static/htmlgraph/

Wellicht staat daar ook meer info over de gebruikte technieken.

[XangadiX]

ik heb voor mijn eindexamen een dergelijk systeem vorm gegeven

http://www.xangadix.net/index2.php?id=01236

mijn idee was om een derde dimensie toe te voegen en je nodes niet te ordenen in cirkels, maar in bollen. Dan heb je altijd genoeg ruimte en kunnen je links nooit 'in de war' raken.

En het ziet er stoer uit

[terabyte]

Ik weet niet of een 'linked network' hetzelfde is als een graaf, maar voor visualisatie van grafen bestaat het programma 'GraphViz'

http://www.graphviz.org/Gallery.php

Maar waarom in JS? Is server-side een plaatje (svg, eps, png) genereren geen optie?

[ Voor 32% gewijzigd door terabyte op 27-07-2006 23:21 ]

[Verwijderd]

het wordt js (met html of svg) of as, iig clientside, want het wordt interactief. Maakt verder voor het algoritme niet zoveel uit natuurlijk

xan: kan je ook iets zeggen over de techniek?

[T.T.]

Wat jij zoekt, is Processing
http://www.processing.org/

JavaScript is een klassiek voorbeeld van het jezelf onnodig moeilijk maken (in ieder geval voor dit probleem). Het voorbeeld van André is bijvoorbeeld met Processing gemaakt. Op de website is de sourcecode ook te vinden en er zijn talloze libraries voor te downloaden. Ik heb zelf ook met Processing gespeeld en als je in Java kan programmeren, dan is het een eitje.

http://www.aharef.info/static/htmlgraph/sourcecode.html

[ Voor 9% gewijzigd door T.T. op 28-07-2006 07:57 ]

[Verwijderd]

heb wat gevonden aan technieken:
http://www.stanford.edu/g...ocumentation/layouts.html

java is helaas ook geen optie, het moet gewoon in elke browser goed werken (zit in een javaloze omgeving). ik zie ook het probleem van js niet zo, behalve wellicht de performance, maar ik denk dat er een heel hoop te optimaliseren valt (bijvoorbeeld door alleen interactie te berekenen voor alle nodes in een cirkel van zeg 100px om de huidige node heen)

komend weekend eens mee spelen

[ Voor 4% gewijzigd door Verwijderd op 28-07-2006 08:22 ]

[T.T.]

Verwijderd schreef op vrijdag 28 juli 2006 @ 07:43:
java is helaas ook geen optie, het moet gewoon in elke browser goed werken. ik zie ook het probleem van js niet zo, behalve wellicht de performance,

Je wilt dat het in elke browser werkt en dan laat je Java vallen voor JavaScript? Ieder z'n ding hoor...
Je maakt het jezelf echt onnodig lastig, maar goed... natuurlijk kun je de code porten naar JavaScript. Ik vind het alleen niet handig om het wiel steeds opnieuw uit te vinden.

[alienfruit]

Misschien kan je kijken om Flash te gebruiken? Ik heb wel eens wat met netwerken gezien gemaakt in Flash. Er is een website [1] waarbij met allemaal computer gegeneerde kunst geschreven in Flash of Processing een voorbeeld is een netwerk van bolletjes [2]. M isschien is dat wel interessant?

[1] http://www.levitated.net
[2] http://www.levitated.net/daily/levPondCode.html

[ Voor 57% gewijzigd door alienfruit op 28-07-2006 11:23 ]

[terabyte]

Verwijderd schreef op vrijdag 28 juli 2006 @ 07:43:
ik zie ook het probleem van js niet zo,

Je bent echt een masochist als je een graaf-visualisatie-algoritme in JS gaat implementeren, JS is helemaal niet bedoeld voor zulke taken.

[André]

terabyte schreef op vrijdag 28 juli 2006 @ 12:23:
[...]


Je bent echt een masochist als je een graaf-visualisatie-algoritme in JS gaat implementeren, JS is helemaal niet bedoeld voor zulke taken.

Ach, qua performance zal het niet geweldig zijn, maar je kunt wel heel veel in JS:

http://www.xs4all.nl/~peterned/examples.html
http://www.xs4all.nl/~peterned/examples/dna.html
http://www.xs4all.nl/~peterned/examples/rotator.html

Ik snap de keuze daarom wel.

[Verwijderd]

De taal waarin het gemaakt wordt is overigens helemaal niet interessant, het gaat mij uiteindelijk om het algoritme, of die nou in as, js of iets anders wordt geschreven zal me in dit stadium een biet zijn, maar ik afgezien van performance geen problemen met js, 't is hoofdzakelijk vectorrekenen wat er moet gebeuren denk ik.

De netwerken blijven tamelijk klein, dus met wat optimalisatie verwacht ik dat het wel te doen is in js

maar goed, het gaat dus meer om de methode, niet om de implementatie

_{man wo say it can not be done should not disturb man doing it}

[ Voor 8% gewijzigd door Verwijderd op 28-07-2006 13:08 ]

[André]

Ik verplaatst het topic naar Wetenschap & Levensbeschouwing omdat je de wetenschappelijke benadering wilt weten en dan heeft het niet veel met Webdesign, Markup & Clientside Scripting te maken

[Verwijderd]

Het zijn inderdaad een soort van graven.
Je kan eens zoeken op gebalanceerde graven en eventueel met zig en zag technieken er punten aan toevoegen
Het nadeel is dat je ontzettend brede graven kunt krijgen (in pyramide vorm)

Waar ga je het voor gebruiken, misschien dat we daar iets mee kunnen

[terabyte]

Verwijderd schreef op vrijdag 28 juli 2006 @ 13:02:
De taal waarin het gemaakt wordt is overigens helemaal niet interessant, het gaat mij uiteindelijk om het algoritme, of die nou in as, js of iets anders wordt geschreven zal me in dit stadium een biet zijn, maar ik afgezien van performance geen problemen met js, 't is hoofdzakelijk vectorrekenen wat er moet gebeuren denk ik.

In de eerste zin van je eerste post wordt meteen een taal gespecificeerd. Vind je het dan vreemd dat ik dan daarop reageer?

Overigens is het onnodig om het wiel opnieuw uit te vinden, zie http://portal.acm.org/citation.cfm?id=63827.63830

_{man wo say it can not be done should not disturb man doing it}

Wat probeer je hiermee te zeggen?

[ Voor 8% gewijzigd door terabyte op 28-07-2006 13:20 ]

[Verwijderd]

Op het plaatje zitten er lussen in je netwerk. Heeft jouw netwerk dat ook? Indien nee, dan is het probleem vrij makkelijk. Beschouw het als een boomstructuur. Dan vervolgens:

1. Kies een root. Elke willekeurige node voldoet als root, maar het handigst is het om als root het element te nemen dat de kortste afstand heeft tot het element dat er het verst vanaf ligt.

2. plot root in oorsprong

3. plot alle nodes die aan root gelinkt zijn op een cirkel rond root, met evenredige afstanden tussen elementen.

4. plot alle elementen die aan elk van de getekende nodes zijn, op een grotere cirkel rond root. Vergroot cirkels indien er nodes over elkaar heen getekend worden.

5. herhaal tot alle elementen getekend zijn.

Dit levert niet meteen het mooiste plaatje op, maar wel iets werkzaams. Vervolgens kan je, afhankelijk van je soort netwerk, wel wat manieren verzinnen om het plaatje te verbeteren

Als je wel lussen hebt in je netwerk, wordt het allemaal lastiger. Het is nog wel te doen zolang elke node ten hoogste in 2 verschillende lussen zit. Dan kan je van tevoren alle lussen inventariseren, beginnen met de grootste lus, in het midden daarvan een imaginaire (niet getekende) root kiezen die zijn centrum heeft in het geometrische midden van die lus met verbindingen naar elk luselement, en vervolgens gaan tekenen tot je weer een lus tegenkomt, dan voor die lus ook weer alle elementen op een cirkel zetten, etc.

Wanneer een node in 3 of meer onafhankelijke lussen kan zitten, werkt deze methode niet meer. Dan wordt het zowiezo theoretisch lastig om je plaatje nog in 2 dimensies te tekenen, en zal je overkruisingen tussen verbindingen moeten accepteren.

[Verwijderd]

even een tussenupdate:

http://www.rikkertkoppes.com/brain2.0/network/net.html (in IE het beste te zien)
wat ik nu doe is het volgende:
- alle linked nodes krijgen een kracht die evenredig is met het verschil van de afstand ertussen met de gewenste afstand van 100
- alle niet linked nodes krijgen een afstotende kracht als ze minder dan 100 uit elkaar zitten, omgekeerd evenredig met de afstand ertussen
- nodes worden verplaatst adhv de totale kracht op een node

dat laat ik nu oneindig doorgaan met een setje van 20 random geplaatste nodes met 20 random links ertussen. daar moet nog een "cooling factor" bij die in een paar stappen van 1 naar 0 gaat, zodat de boel uiteindelijk stabiel blijft (hij wordt nu al redelijk stabiel vind ik)

op zich ben ik niet heel ontevreden over het resultaat tot nu toe, ik ga nog wat puzzelen met andere algoritmes

@Terabyte: de taal is in zoverre niet relevant dat een algorithme in elke taal te implementeren valt, of ik dit nu in js, as, php, c++ of wat dan ook doe, maakt niet uit voor de discussie. Uiteindelijk ben ik wel van plan het met js te doen (met svg waarschijnlijk - IE doe ik dat op de methode als nu en Fx en opera kunnen gewoon wel svg)

[ Voor 19% gewijzigd door Verwijderd op 29-07-2006 17:17 ]

[Verwijderd]

Ik ben nu wat aan het lezen over die KK methode, maar het is me nog niet helemaal duidelijk hoe die onderscheid maakt tussen verbonden vertices en niet verbonden vertices.

Iemand hier een verheldering op?

ter verduidelijking, KK gaat voor zover ik begrijp uit van het minimaliseren van de energiefunctie van alle nodes die gevormd wordt door de veerenergie van alle paren:

E = sum( 0.5 C u²)

waarin u de uitwijking is tov een vastgestelde ideale lengte.
voor zover ik begrijp gaat die som over alle paren en niet alleen de gelinkte.


edit:
na de boel nog een paar keer gelezen te hebben: die vastgestelde ideale lengte is weer evenredig met het kortste aantal links tussen 2 nodes. (de verzameling van die afstande wordt wel de dissimilarity matrix genoemt)

verschuift dus de vraag naar hoe je die zo slim mogelijk kan bepalen

[ Voor 67% gewijzigd door Verwijderd op 31-07-2006 18:48 ]

[Verwijderd]

Die matrix kan je dus met het Floyd-Warshall algorithme bepalen. Probleem is alleen: hij duur O(n^3), dus echt lekker schaalt het niet. Een testje met 100 nodes bleef na optimaliseren 1,5 seconde duren. Kan je nagaan hoe het wordt als meer nodes erin stopt.

Verder heb je dan nog niet eens iets, want je moet de energie nog gaan minimaliseren, dus dat schiet ook niet zo op.

Na verder lezen kwam ik op een andere methode, die van Fructerman-Reingold (pdf). Lijkt behoorlijk op wat ik al geimplementeerd had, dus ik ga daar maar even op verder. Heeft ook als voordeel dat het redelijk schaalbaar is (je hoeft bijvoorbeeld niet weer shortest paths uit te gaan rekenen als er een node of links bijkomen). En ik wou de boel namelijk wel zo bouwen. Nodes komen namelijk van de server af (gedurende een bepaalde tijd mbv snail http/comet) en ik wil dus steeds updaten.

iemand verder nog input?

[ Voor 5% gewijzigd door Verwijderd op 02-08-2006 13:04 ]