¿Cómo visualizo grupos de usuarios?

Question

Tengo una aplicación en la que los usuarios interactúan entre sí.Quiero visualizar estas interacciones para poder determinar si existen grupos de usuarios (dentro de los cuales las interacciones son más frecuentes).

Asigné un punto 2D a cada usuario (donde cada coordenada está entre 0 y 1).Mi idea es que los puntos de dos usuarios se acerquen cuando interactúan, una "fuerza atractiva", y simplemente reviso mis registros de interacción una y otra vez.

Por supuesto, necesito una "fuerza repulsiva" que también separe a los usuarios; de lo contrario, todos colapsarán en un solo punto.

Primero intenté monitorear la más baja y la más alta de cada una de las coordenadas XY y normalizar sus posiciones, pero esto no funcionó, algunos usuarios con una pequeña cantidad de interacciones se quedaron en los bordes y el resto colapsó en el medio.

¿Alguien sabe qué ecuaciones debo usar para mover los puntos, tanto para la fuerza "atractiva" entre los usuarios cuando interactúan, como para una fuerza "repulsiva" para evitar que todos colapsen en un solo punto?

Editar:En respuesta a una pregunta, debo señalar que estoy tratando con aproximadamente 1 millón de usuarios y aproximadamente 10 millones de interacciones entre usuarios.Si alguien puede recomendarme una herramienta que pueda hacer esto por mí, soy todo oídos :-)

Answer 1

En el pasado, cuando probé este tipo de cosas, usé un modelo de resorte para unir nodos vinculados, algo como: dx = -k*(x-l). dx es el cambio de posición, x es la posición actual, l es la separación deseada, y k es el coeficiente del resorte que modificas hasta obtener un buen equilibrio entre la fuerza del resorte y la estabilidad, será inferior a 0,1.Teniendo l > 0 garantiza que no todo quede en el medio.

Además de eso, una fuerza "repulsiva" general entre todos los nodos los extenderá, algo como: dx = k / x^2.Esto será más grande cuanto más cerca estén dos nodos, modifique k para conseguir un efecto razonable.

Answer 2

Puedo recomendar algunas posibilidades:Primero, intente escalar logarítmicamente las interacciones o ejecutarlas a través de una función sigmoidea para reducir el rango.Esto le dará una distribución visual más suave del espaciado.

Independiente de este problema de escala:Mire algunas de las estrategias de renderizado en Graphviz, particularmente los programas "neato" y "fdp".Desde la página de manual:

  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).

Finalmente, considere una de las estrategias de escala, una fuerza de atracción y algún tipo de coeficiente de resistencia en lugar de una fuerza de repulsión.En realidad acercando las cosas y luego, posiblemente, más adelante puede obtener un comportamiento cíclico.

Considere un modelo en el que todo voluntad eventualmente colapsar, pero lentamente.Luego simplemente ejecute hasta que se cumpla alguna condición (un nodo cruza el centro de la región de diseño o algo así).

La resistencia o el impulso pueden codificarse simplemente como una resistencia básica al movimiento y equivalen a estrangular los movimientos;se puede aplicar de manera diferencial (las cosas pueden moverse más lento según qué tan lejos han llegado, dónde se encuentran en el espacio, cuántos otros nodos hay cerca, etc.).

Espero que esto ayude.

Answer 3

El modelo de resorte es la forma tradicional de hacer esto:Haga una fuerza de atracción entre cada nodo en función de la interacción y una fuerza de repulsión entre todos los nodos en función del cuadrado inverso de su distancia.Luego resuelve, minimizando la energía.Es posible que necesite una programación bastante potente para obtener una solución eficiente si tiene más de unos pocos nodos.Asegúrese de que las posiciones iniciales sean aleatorias y ejecute el programa varias veces:Un caso como este casi siempre tiene varios mínimos de energía locales y usted quiere asegurarse de tener uno bueno.

Además, a menos que tengas sólo unos pocos nodos, haría esto en 3D.Una dimensión adicional de libertad permite mejores soluciones, y debería poder visualizar grupos en 3D tan bien, si no mejor, que en 2D.