Lecture 2: Graph Theory
http://sanghyukchun.github.io/48/
(network=graph)는 vertex(=node)와 그것들을 잇는 edge(=link)로 구성되어 있는 일종의 collection.
ANN 역시
뉴런,neuron과
시냅스,synapse로 이루어진 graph.
G=(V,E)로 정의
V : vertex
E : edge
n, m 표기법도 쓰는데 이 때는
n : vertex의 개수
m : edge의 개수
directed_graph / undirected_graph 언급
directed graph 중에서 acyclic directed graph = directed acyclic graph = DAG 언급
graph의 edge는
가중값,weight을 가짐, ex. :
인터넷에선 data flow의 양
social network에선 두 사람 간의 contact가 얼마나 많은지
지리적 그래프에선 단순히
거리,distance를 뜻하기도.
DAG는 항상 triangular matrix로 표현된다.
삼각행렬,triangular_matrix
이것의
고유값,eigenvalue은 diagonal elements들인데 이게 모두 0이 됨 - 따라서, 어떤 graph가 DAG인지 여부를 판단하려면, 모든 eigenvalues들이 0인지만 확인하면 된다.
cocitation : directed_graph 의 vertex i와 j를 동시에 가리키는 vertex들의 개수.
bibliographic_coupling : (위와 반대 방향으로 생각한 것) i와 j가 동시에 가리키는 vertex들의 개수.
hypergraph : hyperedge 가 존재하는 graph.
hyperedge : 하나의 edge가 둘보다 많은(3개 이상?)의 vertex에 연결된 그런 edge.
bipartite_network : hypergraph 를 표현하는 방법 중 하나.
vertex를 두 그룹으로 나누어, 그룹 안에는 edge가 존재하지 않으며, 모든 edge가 그룹 사이에만 존재하는 graph.
같이 묶인 것 끼리는 연결이 없고, 같이 묶이지 않은 것 사이에만 연결이 있는? chk
bipartite matrix에는 incidence_matrix 가 존재한다.
incidence_matrix 를 projection 을 위해 사용할 수 있다.
projection :
edge들끼리 같은 vertex를 가지고 있는지 여부, 혹은 그 반대로
vertex들끼리 같은 edge를 가지고 있는지 여부로 새로운 형태의 그래프를 그리는 것을 의미.
트리,tree : connected, undirected_network 의 일종, closed_loop 가 존재하지 않는 graph.
parent가 단 하나만 존재하는 graph.
planar_network : 서로 교차하는 edge가 하나도 없게 그릴 수 있는 graph.
트리,tree는 planar_graph 의 일종.
planar_graph 는 4-coloring 보다 많은 색을 칠하는 것이 불가능하다는 것이 증명되어 있음.
graph가 planar인지 판단하는 방법 - Kuratowski_theorem
평면그래프,planar_graph
degree : vertex와 연결된 모든 edge의 수.
rel. density ( graph_density ?) = connectance : 전체 존재 가능한 edge와 실제 존재하는 edge(수?)의 비율
mklink
밀도,density
CHK : graph에서 density와 connectance 뜻이 완전히 같은지.
그래서 이걸로 dense_graph , sparse_graph 가 나뉨?? chk
indegree , outdegree :
edge의 방향이 존재하는, 즉 directed_graph 에서만 정의
vertex에 대해 정의됨? chk
indegree : 어떤 vertex가 point하는 vertex의 수
outdegree : 어떤 vertex를 point하는 vertex의 수
경로,path graph_path
vertex들의 sequence인데, 그 모든 consecutive vertex pair가 connected edge인 - 연결된 그래서 edge가 존재하는 - ?
path의
길이,length는 개수가 아니라 edge들의
가중값,weight들의
합,sum으로 정의, 일반적으로.
geodesic_path
shortest_path 의 일종인데, 이 때 shortest path를 weights의 sum이 아니라 단순히 hop 개수만 세는 방법으로 계산하는 것.
일반적으로 graph 의 diameter - graph_diameter - 를 측정할 때 이 값을 사용. (QQQ 다른 graph diameter 표현 방식은?)
Eulerian_path
모든 edge를 정확히 한 번만 visit할 수 있는 path.
rel. 한붓그리기 , 쾨니히스베르크의 다리 문제 ? chk
Hamiltonian_path
모든 vertex를 한 번씩 visit하는 path. .....한번씩만? 적어도한번? chk
이것(eulerian? hamiltonian?)은 다음 문제에 응용가능한데, path를 찾는 것이 NP완전,NP-complete 이라 보통 approximation_algorithm 을 쓴다고.
job_sequencing garbage_collection parallel_programming
component : graph의 subgraph를 뜻함.
outcomponent out-component : 특정 vertex에서 시작해 도달 가능한 vertex들의 set.
incomponent in-component : 특정 vertex로 도달 가능한 path를 가지는 vertex들의 set.
그래프에서 두
경로,path에 대한
독립,independence
edge_independence : 두 path가 서로 공유하는 edge가 없는 경우.
vertex_independence : 두 path가 서로 공유하는 vertex가 없는 경우.
vertex independet하면 edge independent하다. but 역은 항상 성립하지 않는다.
connectivity : (위 상황에서) 주어진 vertex pair 사이에 존재하는 모든 independent path의 개수. /// 그럼 얼마나 '갈 수 있는 길들'이 많은지 여부?
즉 두 vertex 에 대해 주어지는 값이며, 둘 사이의 병목,bottleneck 을 판단할 수 있는 지표.
cut_set
그에 속하는 vertex혹은 edge를 제거했을 때 특정한 vertex pair가 끊어지는 set.
minimum_cut_set , minimum_vertex_cut_set { Compare: minimum_edge_cut_set }
그런 cut set 중에서 가장 작은 element를 가지는 cut set.
Menger_theorem ....
https://www.google.com/search?q=menger's theorem
에 따르면, 주어진 vertex pair의 minimum_vertex_cut_set 의 크기는, 같은 pair의 connectivity 와 같다고.
maxflow max-flow max_flow maximum_flow
두 vertex사이의 edge-independent path 개수 곱하기 capacity.
MKLINK maximum_flow_problem
max-flow/min-cut theorem ....
https://www.google.com/search?q=max-flow/min-cut theorem
에 따르면, vertex pair의 maximum_flow 는 항상 minimum_cut_set (QQQ minimum_vertex_cut_set ?) 과 single path(?? 정의?)의 capacity의 곱과 같다.
이 때 undirected_graph 에 대해서 edge_connectivity 와 minimum_edge_cut_set 의 size와 maximum_flow 의 크기가 같다는 것이 증명될 수 있다.
graph_Laplacian
Lecture 3: Measures and Metric
http://sanghyukchun.github.io/49/
Measure(
측도,measure) and metric(
계량,metric? or
거리,metric?)
measure와 metric의 이 글에서 말하는 중요성은 다음과 같다. 그래서 closeness , betweenness , clustering_coefficient 정도만 커버하고 싶지만 더 한다 함.
- 임의의 그래프를 측정하고 어떤 그래프인지 판단하는 데 필요
- 어떤 vertex가 중요한지 알아낼 수 있음 - 나중에 그 vertex에 주목해서 처리해야 하는 게 있다고.
degree_centrality
가장 먼저 살펴보는 centrality . 단순한데, 얼마나 많이 연결되어있는지를 측정하는 centrality에 불과.
directed_graph 의 경우는 indegree + outdegree.
상황에 따라 indegree_centrality 와 outdegree_centrality 를 정의할 수도 있다.
eigenvector_centrality
Katz_centrality
위 eigenvector_centrality 의 단점: directed_graph 에서 outdegree = 0이고 indegree > 0이어도 eigenvector_centrality 를 계산하면 0이 된다는 단점.
너무 작은 값을 가지는 것을 해결함. (? chk)
MKLINK
Katz_index
PageRank
Katz_centrality 의 단점을 해결.
이상 위 네 metric을 표로 정리하면,
| | with constant term | without constant term |
| divide by outdegree | PageRank | degree_centrality |
| no division | Katz_centrality | eigenvector_centrality |
i.e.
| | 상수항 있음 | 상수항 없음 |
| outdegree로 나눔 | PageRank | degree_centrality |
| 나누지 않음 | Katz_centrality | eigenvector_centrality |
authority ..... graph_authority
무언가 유용한 정보를 가진 vertex. directed_network 에만 존재.
hub ..... graph_hub
authority 중 최고를 찾을 수 있는 곳이 어디인지 알려줄 수 있는 vertex들. directed_network 에만 존재.
authority_centrality , hub_centrality 를 정의함.
closeness_centrality
한 vertex에서 다른 모든 vertex까지의
최단경로,shortest_path의 mean distance. 여기서 distance는 geodesic_path = minimal_hop .
betweenness_centrality
graph에 존재하는 모든
최단경로,shortest_path들에 대해, 한 vertex가 얼마나 많이 그 경로에 속하는지를 나타내는 지표.
중요해 보이지만 찾아내기 어렵다.
clique
모든 vertex들이 fully connected된 vertex set.
k-plex
모두 연결은 안되었어도 ... 일종의 approximated clique.
k-core
(n-k) plex.
k-component
모든 vertex들끼리 적어도 k개의 vertex independent path를 가지는
부분집합,subset.
component .... graph_component
(그래프이론에서 component란 단순히...) 어떤
경로,path를 통해 다른 구성원
(QQQ vertex? 아님 vertex or edge 둘다?) 에 도달할 수 있으면 그것을 component 라고 한다. 즉 어떤 k-component 안에 있는 임의의 vertex는 같은 k-component에 존재하는 다른 임의의 vertex로 반드시 갈 수 있다.
network backbone은 대개 높은 k를 가지는 k-component라고 한다.
transitivity .... graph_transitivity
vertex u - v - w 가 연결되어 삼각형을 만들 때 얘기. 여기서 perfect_transitivity 와 partial_transitivity 정의 가능하며 partial_rate 를 측정할수도.
MKLINK
transitivity(전이성 OR 추이성, pagename tbd.) and
추이관계,transitive_relation
clustering_coefficient -
clustering_coefficient
(이하 cc는 이걸 의미하는 듯.)
얼마나 graph가 뭉쳐있는지를 알아보는
계수,coefficient
정의: '삼각형을 이룰 것 같은'(?) vertex set 중에서 실제 삼각형을 이루는 vertex set의 비율
local_clustering_coefficient
local한 정의.
(number of pairs of neighbors of i that are connected) / (number of pairs of neighbors of i)
(본문에 local cc가 이것인 듯)
"내 친구와 다른 친구가 서로 친구일 확률" 그래서 degree가 높은 vertex는 낮은 local cc를 가질 확률이 높아진다고.
redundancy .... graph_redundancy
neighbor에서 다른 neighbor간의 connection의 평균
global clustering_coefficient 는 local clustering_coefficient 의 summation.
MKLINK
여유도,redundancy
reciprocity .... graph_reciprocity
directed_network 에서 길이 2짜리 loop이 얼마나 많은지.
즉 서로가 서로를 가리키는 vertex의 개수가 얼마나 되는지.
structural_balance
edge를
(edge의 weight?) -1과 1 둘로 정의하고
-1은 서로 enemy
+1은 서로 friend라 하자.
이 때 어떤
루프,loop가 있을 때, 여기에 -1인 edge가
짝수개 있으면 stable하고 - structural_balance
홀수개 있으면 unstable해진다.
대부분의 social network는 이런 balanced한 상황이라고.
Harary_theorem
이런 balanced_network 가 같은 그룹은 positive한 connection만 가지고, 다른 그룹끼리는 negative한 connection만 가지는 그룹들로 나뉜다. 는 정리.
cosine_similarity ....
코사인유사도,cosine_similarity
(이하 작성이 안 되어 있음.. 2014년 이후로 update 없음을 보면 앞으로도...)