[Day22] 페이지랭크 & 전파 모델

[Day22] 페이지랭크 & 전파 모델

• 검색 엔진에서는 그래프를 어떻게 활용할까?_(PageRank)

  • https://n-brogrammer.tistory.com/101

• 그래프를 바이럴 마케팅에 어떻게 활용할까?_(전파 모델)

  • https://n-brogrammer.tistory.com/102

 

 

중요

NetworkX

import networkx as nx
# 방향성이 있는 그래프
G = nx.DiGraph()

# 간선 추가
G.add_edges_from([(1, 4),(1,3),(2, 5), (5, 6),(1, 5)])

print(G.nodes)
>>> [1, 4, 3, 2, 5, 6]

print(G.edges)
>>> [(1, 4), (1, 3), (1, 5), (2, 5), (5, 6)]

 

이 그래프를 그림으로 확인해 보면 아래와 같다.

#그래프 그리기
nx.draw(G, with_labels = True)

 

📌 부분 그래프 구하기

여기서 node_key를 포함하는 부분 그래프를 구하는 함수는 아래와 같고 그림으로 결과를 확인해 보자

# 부분 그래프 구하기
sub=G.subgraph([1,2,4,5])

#그래프 그리기
nx.draw(sub, with_labels = True)

 

• subgraph()함수를 통해서 인자로 원하는 node의 값을 넣어주면 위와 같이 subgraph를 구해 준다.

 

📌 페이지 랭크

페이지 랭크를 라이브러리에 제공하는 함수를 이용하여 구할 수 있다.

# pagerank값 구하기
pr = nx.pagerank(G, alpha = 0.9) 

pr
>>> {1: 0.10224964734220761,
>>>  4: 0.13292447067811508,
>>>  3: 0.13292447067811508,
>>>  2: 0.10224964734220761,
>>>  5: 0.22494894068583754,
>>>  6: 0.30470282327351667}

• 여기서 alpha값은 감폭 비율을 의미한다. 자세한 내용은 위 pagerank링크에서 확인해 보자

 

 

피어세션

• 백준 13711번: LCS4 문제를 풀고 토론을 진행하였다.

from bisect import bisect_left as bl
import sys

def lcs4():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    tmp = [0 for _ in range(N+1)]

    for i in range(N):
        tmp[B[i]] = i
    A=[tmp[A[i]] for i in range(N)]

    lis=[-float('inf')]
    for num in A:
        if lis[-1] < num:
            lis.append(num)
        else:
            lis[bl(lis,num)]=num

    print(len(lis)-1)
lcs4()