Wie visualisiere ich Nutzercluster?

Question

Ich habe eine Anwendung, in der Benutzer miteinander interagieren. Ich möchte diese Interaktionen visualisieren, damit ich feststellen kann, ob es Cluster von Nutzern gibt (innerhalb derer Interaktionen häufiger vorkommen).

Ich habe jedem Benutzer einen 2D-Punkt zugewiesen (wobei jede Koordinate zwischen 0 und 1 liegt). Meine Idee ist, dass sich die Punkte von zwei Nutzern einander annähern, wenn sie interagieren, eine "anziehende Kraft", und ich gehe einfach immer wieder meine Interaktionsprotokolle durch.

Natürlich brauche ich auch eine "abstoßende Kraft", die die Nutzer auseinander treibt, sonst würden sie alle zu einem einzigen Punkt zusammenfallen.

Zuerst habe ich versucht, die niedrigsten und höchsten XY-Koordinaten zu überwachen und ihre Positionen zu normalisieren, aber das hat nicht funktioniert, ein paar Benutzer mit einer geringen Anzahl von Interaktionen blieben an den Rändern, und der Rest kollabierte in der Mitte.

Weiß jemand, welche Gleichungen ich verwenden sollte, um die Punkte zu bewegen, sowohl für die "anziehende" Kraft zwischen den Nutzern, wenn sie interagieren, und eine "abstoßende" Kraft, um zu verhindern, dass sie alle in einen einzigen Punkt kollabieren?

Edit: Als Antwort auf eine Frage sollte ich darauf hinweisen, dass ich es mit etwa 1 Million Benutzern und etwa 10 Millionen Interaktionen zwischen Benutzern zu tun habe. Wenn jemand ein Tool empfehlen kann, das dies für mich tun könnte, bin ich ganz Ohr :-)

Answer 1

In der Vergangenheit habe ich, wenn ich so etwas versucht habe, ein Federmodell verwendet, um verbundene Knoten zusammenzuziehen, etwa so: dx = -k*(x-l) . dx ist die Veränderung der Position, x ist die aktuelle Position, l ist die gewünschte Trennung, und k ist der Federkoeffizient, den Sie so lange verändern, bis Sie ein ausgewogenes Verhältnis zwischen Federstärke und Stabilität erreicht haben. Er wird unter 0,1 liegen. Mit l > 0 sorgt dafür, dass nicht alles in der Mitte landet.

Darüber hinaus wird eine allgemeine "abstoßende" Kraft zwischen allen Knoten diese verteilen, etwa so: dx = k / x^2 . Dieser ist umso größer, je näher zwei Knoten beieinander liegen, tweak k um eine angemessene Wirkung zu erzielen.

Answer 2

Ich kann Ihnen einige Möglichkeiten empfehlen: Versuchen Sie zunächst, die Interaktionen logarithmisch zu skalieren oder sie durch eine Sigmoidalfunktion laufen zu lassen, um den Bereich zu verkleinern. Dadurch erhalten Sie eine glattere visuelle Verteilung der Abstände.

Unabhängig von diesem Skalierungsproblem: Sehen Sie sich einige der Rendering-Strategien in Graphviz an, insbesondere die Programme "neato" und "fdp". Aus der Manpage:

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

Schließlich sollte man eine der Skalierungsstrategien in Betracht ziehen, nämlich eine anziehende Kraft und eine Art Widerstandskoeffizient anstelle einer abstoßenden Kraft. Die Dinge tatsächlich näher zusammenrücken y dann möglicherweise weiter später kann man nur zyklisches Verhalten bekommen.

Betrachten wir ein Modell, bei dem alles se irgendwann zusammenbrechen, aber langsam. Dann laufen Sie einfach, bis eine Bedingung erfüllt ist (ein Knoten kreuzt die Mitte des Layoutbereichs oder ähnliches).

Luftwiderstand oder Schwungkraft können einfach als grundlegender Bewegungswiderstand kodiert werden und auf eine Drosselung der Bewegungen hinauslaufen; sie können differenziert angewendet werden (Dinge können sich langsamer bewegen, je nachdem, wie weit sie gegangen sind, wo sie sich im Raum befinden, wie viele andere Knoten in der Nähe sind usw.).

Ich hoffe, das hilft.

Answer 3

Das Federmodell ist der traditionelle Weg, um dies zu tun: Machen Sie eine anziehende Kraft zwischen jedem Knoten auf der Grundlage der Wechselwirkung und eine abstoßende Kraft zwischen allen Knoten auf der Grundlage des inversen Quadrats ihrer Entfernung. Lösen Sie dann die Aufgabe und minimieren Sie die Energie. Wenn Sie mehr als ein paar Knoten haben, benötigen Sie möglicherweise eine ziemlich leistungsstarke Programmierung, um eine effiziente Lösung zu erhalten. Stellen Sie sicher, dass die Startpositionen zufällig sind, und führen Sie das Programm mehrere Male aus: Ein Fall wie dieser hat fast immer mehrere lokale Energieminima, und Sie wollen sichergehen, dass Sie ein gutes gefunden haben.

Wenn Sie nicht nur ein paar Knoten haben, würde ich das in 3D machen. Eine zusätzliche Dimension der Freiheit ermöglicht bessere Lösungen, und Sie sollten in der Lage sein, Cluster in 3D genauso gut, wenn nicht sogar besser als in 2D zu visualisieren.