Come posso visualizzare cluster di utenti?

Question

Ho un'applicazione in cui gli utenti interagiscono tra loro.Voglio visualizzare queste interazioni in modo da poter determinare se esistono cluster di utenti (all'interno dei quali le interazioni sono più frequenti).

Ho assegnato un punto 2D a ciascun utente (dove ciascuna coordinata è compresa tra 0 e 1).La mia idea è che i punti di due utenti si avvicinino quando interagiscono, una "forza attrattiva", e io controllo ripetutamente i miei registri di interazione ancora e ancora.

Naturalmente, ho bisogno di una "forza repulsiva" che allontani anche gli utenti, altrimenti collasseranno tutti in un unico punto.

Per prima cosa ho provato a monitorare il punto più basso e quello più alto di ciascuna delle coordinate XY e a normalizzare le loro posizioni, ma non ha funzionato, alcuni utenti con un numero limitato di interazioni sono rimasti ai bordi e il resto è crollato tutto al centro.

Qualcuno sa quali equazioni dovrei usare per spostare i punti, sia per la forza "attrattiva" tra gli utenti quando interagiscono, sia per una forza "repulsiva" per impedire che collassino tutti in un unico punto?

Modificare:In risposta ad una domanda, tengo a precisare che ho a che fare con circa 1 milione di utenti, e circa 10 milioni di interazioni tra utenti.Se qualcuno può consigliarmi uno strumento che potrebbe fare questo per me, sono tutt'orecchi :-)

Answer 1

In passato, quando ho provato questo genere di cose, ho utilizzato un modello a molla per unire i nodi collegati, qualcosa del tipo: dx = -k*(x-l). dx è il cambiamento di posizione, x è la posizione attuale, l è la separazione desiderata, e k è il coefficiente della molla che modifichi finché non ottieni un buon equilibrio tra resistenza e stabilità della molla, sarà inferiore a 0,1.Avendo l > 0 fa sì che tutto non finisca a metà.

In aggiunta a ciò, una forza "repulsiva" generale tra tutti i nodi li allargherà, qualcosa del tipo: dx = k / x^2.Questo sarà più grande quanto più vicini saranno i due nodi, modifica k per ottenere un effetto ragionevole.

Answer 2

Posso consigliare alcune possibilità:per prima cosa, prova a ridimensionare logaritmicamente le interazioni o a eseguirle attraverso una funzione sigmoidale per ridurre l'intervallo.Ciò ti darà una distribuzione visiva più fluida della spaziatura.

Indipendentemente da questo problema di ridimensionamento:guarda alcune delle strategie di rendering in graphviz, in particolare i programmi "neato" e "fdp".Dalla pagina man:

  neato  draws  undirected graphs using ``spring'' models (see Kamada and
  Kawai, Information Processing Letters 31:1, April 1989).   Input files
  must  be  formatted  in the dot attributed graph language.  By default,
  the output  of  neato  is  the  input  graph  with  layout coordinates
  appended.

  fdp  draws  undirected  graphs using a ``spring'' model. It relies on a
  force-directed approach in the spirit of Fruchterman and Reingold  (cf.
  Software-Practice & Experience 21(11), 1991, pp. 1129-1164).

Infine, consideriamo una delle strategie di ridimensionamento, una forza attrattiva e una sorta di coefficiente di resistenza invece di una forza repulsiva.In realtà avvicinando le cose E allora forse più tardi potresti semplicemente ottenere un comportamento ciclico.

Considera un modello in cui tutto Volere collasserà alla fine, ma lentamente.Quindi esegui finché non viene soddisfatta una condizione (un nodo attraversa il centro della regione di layout o qualcosa del genere).

La resistenza o lo slancio possono essere semplicemente codificati come una resistenza di base al movimento e equivale a limitare i movimenti;può essere applicato in modo differenziale (le cose possono muoversi più lentamente in base a quanto sono andate lontano, a dove si trovano nello spazio, a quanti altri nodi sono vicini, ecc.).

Spero che questo ti aiuti.

Answer 3

Il modello a molla è il modo tradizionale per farlo:creare una forza attrattiva tra ciascun nodo in base all'interazione e una forza repulsiva tra tutti i nodi in base all'inverso del quadrato della loro distanza.Quindi risolvere, minimizzando l'energia.Potrebbe essere necessaria una programmazione abbastanza potente per ottenere una soluzione efficiente se si dispone di più di pochi nodi.Assicurati che le posizioni iniziali siano casuali ed esegui il programma più volte:un caso come questo contiene quasi sempre diversi minimi energetici locali e vuoi assicurarti di averne uno buono.

Inoltre, a meno che tu non abbia solo pochi nodi, lo farei in 3D.Un'ulteriore dimensione di libertà consente soluzioni migliori e dovresti essere in grado di visualizzare i cluster anche in 3D, se non meglio di 2D.