Como determinar prováveis ​​conexões em uma rede social?

Estou curioso em determinar uma abordagem para enfrentar um algoritmo de "amigos sugeridos".

O Facebook possui um recurso no qual recomendará a você indivíduos com os quais acha que pode estar familiarizado. Esses usuários normalmente (excluindo os casos extremos nos quais um usuário recomenda especificamente a um amigo ) têm uma rede altamente semelhante à sua. Ou seja, o número de amigos em comum é alto. Presumo que o Twitter siga um caminho semelhante para o mecanismo "Quem seguir".

Stephen Doyle (Igy) , um funcionário do Facebook, sugeriu que o feed de notícias relacionado que usa a fórmula do EdgeRank, o que parece indicar que mais deve ser valorizado do que amigos, como aparência, são posts semelhantes. Outro usuário sugeriu o sistema Google Rank.

O Facebook declara a Otimização do feed de notícias como em que$\sum u_{e}w_{e}d_{e}$

$u_{e}$ = pontuação de afinidade entre o usuário visualizador e o criador da borda = peso dessa borda (criar, comentar, , marcar etc.) = fator de redução de tempo com base em quanto tempo a borda foi criada
$w_{e}$
$d_{e}$

A soma desses itens deve fornecer a classificação de um objeto, que eu suponho como Igy sugeriu, significa que algo em um formato semelhante é usado para os amigos sugeridos.

Então, acho que é dessa maneira que as conexões para todos os tipos são feitas em geral por meio de um sistema de classificação?

Você pode pensar no gráfico social como uma matriz . Uma abordagem para o problema é primeiro calcular , que fornecerá todos os caminhos de comprimento dois entre dois atores na rede social. Isso pode ser visto como o peso da conexão entre esses amigos de amigos. O próximo passo é selecionar as colunas da linha correspondentes à pessoa de seu interesse para obter os melhores candidatos para novos amigos.M 2 M$\mathbf{M}$$\mathbf{M}^2$$\mathbf{M}^2$

O que você está procurando é uma heurística. Nenhum algoritmo pode dizer, dado um gráfico de amigos como a única entrada, se dois indivíduos não conectados diretamente são amigos ou não; não é garantido que a relação amizade / conhecimento seja transitiva (podemos assumir simetria, mas isso pode até ser um exagero na vida real). Qualquer boa heurística precisará, portanto, basear-se no entendimento de como as pessoas interagem, em vez de algum entendimento matemático da natureza dos gráficos de relações (embora seja necessário quantificar a heurística nesses termos).

Sugerir amigos de amigos com igual probabilidade é uma heurística relativamente barata, mas imprecisa. Por exemplo, meu pai tem amigos, mas eu não diria que sou amigo de nenhum deles (embora eu provavelmente diria que sou amigo de meu pai para fins de, por exemplo, uma rede social). Ter uma pessoa a uma distância relativamente próxima não necessariamente a torna uma ótima candidata.

Sugerir pessoas com quem você tem muitas conexões estendidas também parece ser uma má escolha em geral, porque isso tende a levar a um crescimento exponencial de amigos de pessoas que seguem adiante (os sete graus de separação do jogo de Kevin Bacon são um exemplo disso).

Eu sugiro um modelo baseado em circuito. Assume-se que cada elo é um resistor de resistência . Então, o melhor candidato para um novo amigo pode ser o indivíduo com a menor resistência equivalente. Aqui está um exemplo de gráfico ASCII mal executado:$R$

  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

Digamos que queremos encontrar novos amigos para a. aOs amigos atuais de b, são c, e f. Nós avaliamos a resistência equivalente líquido entre ae cada um d, e, g, h, e i:

pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

De acordo com essa heurística, dé o melhor candidato amigo, seguido de perto por h. gé a próxima melhor aposta, seguida de perto por e. inunca pode ser um amigo candidato por essa heurística. Se você considera os resultados dessa heurística representativos de interações sociais humanas reais, é importante. Em termos computacionais, isso envolveria a localização de um subgrafo contendo todos os caminhos entre dois indivíduos (ou, talvez curiosamente, algum truncamento significativamente selecionado disso) e, em seguida, a avaliação da resistência equivalente entre os nós de origem e coletor.

EDIT: Então, qual é a minha motivação social para isso? Bem, esse pode ser um modelo aproximado de quão difícil é entrar em contato e, posteriormente, comunicar quantidades significativas de informações por meio de intermediários (amigos). Em termos de CS (em vez de termos de física), isso pode ser interpretado como largura de banda entre dois nós em um gráfico. As extensões desse sistema permitiriam diferentes tipos de links entre pessoas com pesos diferentes (resistência, largura de banda etc.) e procedessem da forma descrita acima.

Há muito trabalho feito sobre esse problema, pois a popularidade das redes sociais decolou. O problema é tipicamente denominado "Previsão de Link" e pesquisas muito boas e abrangentes podem ser encontradas aqui e aqui . Os métodos variam do muito simples (por exemplo, semelhança de Jaccard entre os nós) até o muito complexo (por exemplo, a construção de modelos estatísticos do processo de conexão generativa). Depende muito dos recursos específicos que você tem disponível no seu conjunto de dados (por exemplo, apenas estrutura de rede, atributos do nó ?, atributos da borda, ...), mas essas pesquisas fornecerão uma boa idéia para começar.

Isenção de responsabilidade: estou supondo muito aqui; Eu não li nenhuma pesquisa de gênero.

Você pode observar quantas conexões com nós compartilham relativamente ao número de conexões que um nó possui. Essa é uma idéia muito ingênua (como local), mas aqui vai.

Todo nó (pessoa ou outro conceito) tem um conjunto de conexões . Agora, dados dois nós e , sugira a seC N N 1 N 2 N 2 N $N$$C_N$$N_1$$N_2$$N_2$$N_1$

$\qquad \displaystyle \frac{|C_{N_1} \cap C_{N_2}|}{|C_{N_1}|} \geq \alpha$

por algum razoável (e vice-versa).$\alpha \in [0,1]$

Outra idéia é mais global: determine um conjunto de nós semelhante ao disponível e proponha conexões que muitos deles compartilham. Então, defina o conjunto de nós semelhantes

$\qquad \displaystyle S_N = \left\{M : \frac{|C_N \cap C_M|}{N} \geq \alpha\right\}$

e o conjunto de sugestões plausíveis de

$\qquad \displaystyle \left\{ S : \frac{\sum_{M \in S_N} [S \in M]}{|S_N|} \geq \beta \right\}$

novamente para razoável .$\alpha, \beta \in [0,1]$

Na realidade, você certamente desejaria ponderar as conexões individualmente; por exemplo, os elementos do quais você já está conectado devem ter uma importação maior do que os que estão longe de você.$S_N$