3

我有一个用户相互交互的应用程序。我想可视化这些交互，以便确定是否存在用户集群（其中交互更频繁）。

我为每个用户分配了一个 2D 点（每个坐标都在 0 和 1 之间）。我的想法是，两个用户的点在交互时会靠得更近，这是一种“吸引力”，我只是一遍又一遍地浏览我的交互日志。

当然，我需要一种“排斥力”来将用户也分开，否则他们将全部坍塌成一个点。

首先，我尝试监控每个 XY 坐标的最低和最高，并将它们的位置归一化，但这没有奏效，少数交互次数很少的用户停留在边缘，其余的都崩溃到中间。

有谁知道我应该使用什么方程来移动这些点，既可以用于用户交互时的“吸引力”，也可以使用“排斥”力来阻止它们全部坍缩成一个点？

编辑：在回答一个问题时，我应该指出我正在处理大约 100 万用户，以及大约 1000 万用户之间的交互。如果有人可以推荐一个可以为我做到这一点的工具，我会全力以赴:-)

4

3 回答 3

2

过去，当我尝试过这种事情时，我使用弹簧模型将链接的节点拉到一起，例如：dx = -k*(x-l). dx是位置的变化，x是当前位置，l是所需的分离，k是你调整的弹簧系数，直到你在弹簧强度和稳定性之间取得很好的平衡，它会小于 0.1。l > 0确保一切都不会在中间结束。

In addition to that, a general "repulsive" force between all nodes will spread them out, something like: dx = k / x^2. This will be larger the closer two nodes are, tweak k to get a reasonable effect.

于 2008-10-06T05:17:47.000 回答
1

我可以推荐一些可能性：首先，尝试对交互进行对数缩放或通过 sigmoidal 函数运行它们以压缩范围。这将为您提供更平滑的间距视觉分布。

独立于这个缩放问题：看看 graphviz 中的一些渲染策略，特别是“neato”和“fdp”程序。从手册页：

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

最后，考虑一种缩放策略、吸引力和某种阻力系数而不是排斥力。实际上，将事物移近，然后可能再移远，可能只会让您产生循环行为。

考虑一个模型，在这个模型中，一切最终都会崩溃，但速度很慢。然后运行直到满足某些条件（一个节点穿过布局区域的中心或类似的）。

阻力或动量可以被编码为对运动的基本阻力，并相当于限制运动；它可以被不同地应用（事情可以根据它们走了多远，它们在空间中的位置，有多少其他节点靠近等等）。

希望这可以帮助。

于 2008-09-18T15:53:42.693 回答
0

The spring model is the traditional way to do this: make an attractive force between each node based on the interaction, and a repulsive force between all nodes based on the inverse square of their distance. Then solve, minimizing the energy. You may need some fairly high powered programming to get an efficient solution to this if you have more than a few nodes. Make sure the start positions are random, and run the program several times: a case like this almost always has several local energy minima in it, and you want to make sure you've got a good one.

Also, unless you have only a few nodes, I would do this in 3D. An extra dimension of freedom allows for better solutions, and you should be able to visualize clusters in 3D as well if not better than 2D.

于 2008-11-27T17:11:16.460 回答