Como faço para visualizar grupos de usuários?

Question

Eu tenho um aplicativo no qual os usuários interagem uns com os-outros. Quero visualizar essas interações para que eu possa determinar se grupos de usuários existe (dentro do qual as interações são mais frequentes).

Eu atribuído um ponto 2D para cada usuário (onde cada coordenada é entre 0 e 1). Minha idéia é que os pontos dois usuários se aproximam quando eles interagem, uma 'força de atração', e eu repetidamente passar por meus registros de interação uma e outra vez.

É claro, eu preciso de uma "força repulsiva" que vai empurrar os usuários além demais, caso contrário, todos eles vão simplesmente entrar em colapso em um único ponto.

Primeiro tentei monitorando o menor e maior de cada uma das coordenadas XY, e normalizando as suas posições, mas isso não funcionou, alguns usuários com um pequeno número de interações ficou nas bordas, eo resto tudo desabou em meio.

Alguém sabe o que equações devo usar para mover os pontos, tanto para a força "atraente" entre os usuários quando eles interagem, e uma força "repulsiva" para pará-los todos em colapso em um único ponto?

Edit: Em resposta a uma pergunta, gostaria de salientar que estou lidando com cerca de 1 milhão de usuários, e cerca de 10 milhões de interações entre usuários. Se alguém pode recomendar uma ferramenta que poderia fazer isso por mim, eu sou todo ouvidos: -)

Answer 1

No passado, quando eu tentei este tipo de coisa, eu usei um modelo mola para puxar os nós ligados entre si, algo como: dx = -k*(x-l). dx é a mudança na posição, x é a posição atual, l é a separação desejada e k é o coeficiente de mola que você ajustar até obter um bom equilíbrio entre a força de mola e estabilidade, vai ser menor do que 0,1. Tendo garante l > 0 que tudo não acabe no meio.

Além disso, uma força geral "repulsiva" entre todos os nós vai espalhá-los para fora, algo como: dx = k / x^2. Este será maior quanto mais próximo dois nós são, k tweak para obter um efeito razoável.

Answer 2

Posso recomendar algumas possibilidades: primeiro, tente as interações ou executá-los através de uma função sigmoidal para esmagar a gama-escala log. Isto lhe dará uma distribuição visual mais suave de espaçamento.

Independente desta questão de escala: olhada em algumas das estratégias renderização em graphviz, designadamente os programas "neato" e "fdp". A partir da página 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).

Finalmente, considere uma das estratégias de escala, uma força atrativa, e algum tipo de coeficiente de arrasto, em vez de uma força repulsiva. Realmente mover as coisas mais perto e , em seguida, possivelmente, mais longe, mais tarde, pode apenas te comportamento cíclico.

Considere um modelo em que tudo irá em colapso eventualmente, mas lentamente. Em seguida, basta correr até que alguma condição for atendida (um nó atravessa o centro da região de layout ou algo assim).

Arraste ou impulso pode simplesmente ser codificado como uma resistência básica ao movimento e quantidade de estrangular os movimentos; ele pode ser aplicado diferencialmente (coisas podem se mover mais lentamente com base em quão longe eles passaram, onde eles estão no espaço, quantos outros nós estão próximos, etc.).

Espero que isso ajude.

Answer 3

O modelo de primavera é a maneira tradicional de fazer isso: fazer uma força de atração entre cada nó baseado na interação, e uma força repulsiva entre todos os nós com base no inverso do quadrado da distância. Em seguida, resolver, minimizando a energia. Você pode precisar de algum bastante elevado de programação potência para obter uma solução eficiente para isso se você tiver mais do que alguns nós. Certifique-se as posições iniciais são aleatórios, e executar o programa várias vezes: um caso como este quase sempre tem vários mínimos de energia local nele, e você quer ter certeza de que você tem uma boa.

Além disso, a menos que você tem apenas alguns nós, gostaria de fazer isso em 3D. Uma dimensão extra de liberdade permite melhores soluções, e você deve ser capaz de visualizar conjuntos em 3D tão bem se não melhor do que 2D.