frhyme

always doing another thing

neo4j - data science - part 4.1

1 분 소요

  • neo4j - data science - part 4에 작성된 link prediction 내용을 번역하여, 정리하였습니다.
  • 이 모듈에서는 citation graph에서 co-authorship을 예측하는 머신러닝 분류기를 만듭니다. 따라서 다음을 배우게 되죠.
    • link prediction이 무엇인지.
    • neo4j에서 link prediction을 위해서 무엇을 쓸 수 있는지.
  • link prediction은 Jon Kleinberg and David Liben-Nowell가 2004년에 쓴 paper로 인해 유명해진 다음, 지금도 꾸준히 연구되고 있는 주제다.
  • 사실, 그래서, 근래에 어떤 node들이 관계를 맺게 될 것인가? 를 예측하는 것이 주목적이며, 노드들간의 proximity를 분석할 수 있는 지표를 개발하는 식으로 진행되어 왔다. 쉽게 말하면, 그냥 어떻게 그 노드간의 거리를 예측할 것인가? 가 목적이라는 이야기죠.
  • 우선 간단하게 네트워크를 만들어봅니다.
UNWIND [["A", "C"], ["A", "B"], ["B", "D"],
        ["B", "C"], ["B", "E"], ["C", "D"]] AS pair
MERGE (n1:Node {name: pair[0]})
MERGE (n2:Node {name: pair[1]})
MERGE (n1)-[:FRIENDS]-(n2)
  • 다음의 3가지 link prediction 알고리즘을 사용해봅니다.

Common Neighbors

  • Common Neighbors: 간단한 알고리즘으로서, 연결되어 있지 않은 두 노드들 간에 공통의 친구들이 공유된다면, 이 둘은 이후에 연결될 가능성이 높다는 것을 말하며, algo.linkprediction.commonNeighbors로 예측할 수 있습니다.
MATCH (a:Node {name: 'A'})
MATCH (d:Node {name: 'D'})
RETURN algo.linkprediction.commonNeighbors(a, d) AS score

Adamic Adar

  • 이 알고리즘은 common neighbors와 유사하나, 그 둘이 각각 가지고 있는 degree(다른 노드들과 얼마나 많이 연결되어 있는지)가 높을수록 서로 연결될 가능성이 낮다고 평가하는 방법입니다.
  • 가령, A와 B간에 공통되는 이웃들이 많다고 하더라도, 이웃들의 degree가 매우 크다면(즉, 이웃이 매우 인기가 많거나 혹은 바쁜 사람이라면), 이 둘이 연결될 가능성은 적어지죠. 반대로 말하자면, 이 둘 간에 공통된 이웃들이 인기가 적으면, 이 둘을 소개시켜줄 가능성이 커집니다.
MATCH (a:Node), (b:Node)
WHERE a <> b AND a.name < b.name AND not((a)-[:FRIENDS]-(b))
RETURN a.name, b.name, algo.linkprediction.adamicAdar(a, b) AS score
ORDER BY score DESC

Preferential Attachment

  • 이는 쉽게, ‘빈익빈 부익부’라고 말할 수 있씁니다. 즉, 가장 영향력이 큰 친구와 친구를 하고 싶은 것이 당연하다, 는 것이죠.
MATCH (a:Node {name: 'C'})
MATCH (d:Node {name: 'E'})
RETURN algo.linkprediction.preferentialAttachment(a, d) AS score

wrap-up

  • 저는 원래, networkx를 주로 사용해서 데이터로부터 graphy feature를 뽑아냅니다. cypher에서 쓰고 있는 대부분의 알고리즘들은 당연히, networkx를 통해서도 적용이 가능한데요, 저에게는 cypher가 아직은 좀 낯설게 느껴지네요.
  • 그래서 좀 이해하다가 좀 귀찮기도 해서 뒤쪽은 약간 대충 마무리했습니다. 흐름은 대충 알겠는데 너무 꼼꼼하게 다 볼 필요는 없다고 생각했거든요.

댓글남기기