Comment visualiser les grappes d'utilisateurs?

Question

J'ai une application dans laquelle les utilisateurs interagissent les uns avec les autres. Je souhaite visualiser ces interactions afin de déterminer s'il existe des groupes d'utilisateurs (au sein desquels les interactions sont plus fréquentes).

J'ai attribué un point 2D à chaque utilisateur (où chaque coordonnée est comprise entre 0 et 1). Mon idée est que les points de deux utilisateurs se rapprochent quand ils interagissent, ce qui constitue une "force attractive", et je consulte mon journal d'interaction à maintes reprises, encore et encore.

Bien sûr, il me faut une "force de répulsion". cela séparera également les utilisateurs, sinon ils s'effondreront tous en un seul point.

J'ai d'abord essayé de surveiller les valeurs les plus basses et les plus hautes de chacune des coordonnées XY et de normaliser leurs positions, mais cela n'a pas fonctionné. Quelques utilisateurs disposant d'un petit nombre d'interactions sont restés sur les bords et le reste s'est tout simplement effondré. au milieu.

Est-ce que quelqu'un sait quelles équations je devrais utiliser pour déplacer les points, à la fois pour le "attractif" et la force entre les utilisateurs quand ils interagissent, et un "répulsif" forcer à les empêcher tous de s'effondrer en un seul point?

Edit: En réponse à une question, je dois signaler que je traite avec environ 1 million d'utilisateurs et environ 10 millions d'interactions entre utilisateurs. Si quelqu'un peut recommander un outil qui pourrait le faire pour moi, je suis tout ouïe: -)

Answer 1

Dans le passé, lorsque j'avais essayé ce genre de chose, j'avais utilisé un modèle Spring pour rassembler des nœuds liés, quelque chose comme: dx = -k * (x-l) . dx est le changement de position, x est la position actuelle, l est la séparation souhaitée et k est le coefficient de ressort que vous ajustez jusqu'à obtenir un bon équilibre entre force et stabilité du ressort, il sera inférieur à 0,1. Avoir l > 0 garantit que tout ne se termine pas au milieu.

En plus de cela, un "répulsif" général une force entre tous les nœuds les répartira, quelque chose comme: dx = k / x ^ 2 . Plus les deux nœuds seront proches, plus elle sera grande, modifiez k pour obtenir un effet raisonnable.

Answer 2

Je peux vous recommander certaines possibilités: essayez d’abord de mettre à l’échelle le journal les interactions ou de les exécuter via une fonction sigmoïde pour réduire la plage. Cela vous donnera une distribution visuelle plus douce de l'espacement.

Indépendamment de cette question d’échelle: examinez certaines des stratégies de rendu de graphviz, en particulier les programmes "neato". et "fdp". À partir de la page de manuel:

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

Enfin, considérons l’une des stratégies de dimensionnement, une force attractive et une sorte de coefficient de traînée au lieu d’une force répulsive. En fait, rapprocher et les choses, puis éventuellement plus loin, risque de vous amener à un comportement cyclique.

Considérons un modèle dans lequel tout tout s'effondrera finalement, mais lentement. Ensuite, exécutez-le jusqu'à ce qu'une condition soit remplie (un nœud traverse le centre de la région de mise en page, par exemple).

La traînée ou l’élan peuvent simplement être codés comme une résistance de base au mouvement et équivalent à une limitation des mouvements; il peut être appliqué différemment (les choses peuvent se déplacer plus lentement en fonction de leur distance, de leur position dans l’espace, du nombre de nœuds proches, etc.).

J'espère que cela vous aidera.

Answer 3

Le modèle de ressort est la méthode traditionnelle pour ce faire: créer une force attractive entre chaque nœud en fonction de l'interaction et une force de répulsion entre tous les nœuds en fonction du carré inverse de leur distance. Alors résolvez en minimisant l'énergie. Vous aurez peut-être besoin d'une programmation assez puissante pour obtenir une solution efficace si vous avez plus que quelques nœuds. Assurez-vous que les positions de départ sont aléatoires et exécutez le programme plusieurs fois: un cas comme celui-ci contient presque toujours plusieurs minima d'énergie locaux et vous voulez vous assurer d'en avoir un bon.

De plus, à moins que vous n'ayez que quelques nœuds, je le ferais en 3D. Une dimension supplémentaire de liberté permet de meilleures solutions et vous devriez également pouvoir visualiser les clusters en 3D, sinon mieux que le 2D.