네트워크과학,network_science,netsci


[edit]

1. Menczer

여기 추가하지 말고 local에 먼저 추가하고 여기에는 그걸 복사해서 업데이트할것.
{
p20

연결의 수에 대해.

complete_network
모든 node의 짝(pair)이 연결된 network.
이 때 최대 link 수는 undirected network에서
$\displaystyle L_{\rm max}=\binom{N}{2}=\frac{N(N-1)}{2}$
directed network에서는 그 두 배이므로
$\displaystyle L_{\rm max}=N(N-1)$

bipartite_network가 complete한 경우. complete_bipartite_network?
이 때는 한 group의 모든 nodes가 다른 그룹의 모든 nodes에 연결되면 되므로, 각 group의 size가 각각 $\displaystyle N_1,N_2$ 라 할 때
$\displaystyle L_{\rm max}=N_1\times N_2$

density of a network, network_density
네트워크의 density란, 가능한 연결 수 중 실제 연결된 수의 비율.
$\displaystyle N$ nodes, $\displaystyle L$ links 라 할 때
$\displaystyle d=\frac{L}{L_{\rm max}}$
undirected network의 density는
$\displaystyle d=\frac{L}{L_{\rm max}}=\frac{2L}{N(N-1)}$
directed network의 density는
$\displaystyle d=\frac{L}{L_{\rm max}}=\frac{L}{N(N-1)}$
따라서
complete_network 에선 $\displaystyle L=L_{\rm max}$ 이므로 $\displaystyle d=1$ 이다.
sparse_network 에선 $\displaystyle L\ll L_{\rm max}$ 이므로 $\displaystyle d\ll 1$ 이다.

sparsity of a network, network_sparsity
수식이 없는데 density의 역수인지???

p22 1.4 Subnetworks

subnetwork = subgraph : subset of a network
노드 중 일부를 가져온 것, 근데 그 노드들 사이의 links는 모두 가져와야 함

clique : a complete subnetwork.
모든 complete_network 의 subnetwork는 clique. (당연)

ego_network : subnetwork의 한 가지. 한 node(=ego)와 그 neighbors로 이루어진 network.

p23 1.5 Degree

degree of a node, node_degree $\displaystyle k_i$
어떤 node의 성질. 그 node의 link(혹은 neighbor)의 수.
기호: node $\displaystyle i$ 의 degree를 $\displaystyle k_i$ 로 표기.
degree가 0인(neighbor가 없는) node는 singleton.

average_degree $\displaystyle \langle k \rangle$
어떤 network의 평균 degree (average_degree)는 $\displaystyle \langle k \rangle$ 로 표기.
$\displaystyle \langle k \rangle = \frac{\sum_i k_i}{N}$
directly proportional to its density.
(보이기) undirected network의 경우, $\displaystyle \sum_i k_i=2L$ 이고 위의 식에서 $\displaystyle 2L=dN(N-1)$ 이므로
$\displaystyle \langle k \rangle = \frac{2L}{N} = \frac{dN(N-1)}{N} = d(N-1)$
그리고
$\displaystyle d=\frac{\langle k \rangle}{N-1}$

p24 1.6 Directed Networks

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
}

[edit]

2. KAIST Network Science 수업 (2014)

대충 요약

Lecture 1: Introduction
http://sanghyukchun.github.io/47/

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
어떤 commodity (?) 혹은 substance (?) 의 flow 가 어떤 비율로 흘러가느냐에 따라 diffusion (MKLINK 확산,diffusion) 을 정의할 수 있다.
- 복잡하므로 링크로 대신한다고... => https://en.wikipedia.org/wiki/Laplacian_matrix#Random_walks_on_graphs
- 저기 첫 줄 " the Laplacian_matrix , also called the graph_Laplacian , admittance_matrix , Kirchhoff_matrix or discrete_Laplacian " 모두 동의어인듯.
MKLINK 라플라시안,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
각 vertex가 다른 vertex와 '결국, 궁극적으로 얼마나 많은 연결,connection을 갖는 지를 확인하는 것.
mklink 고유벡터,eigenvector
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
유사도,similarity는 서로 다른 graph가 얼마나 비슷한지를 측정하는 것.
코사인,cosine은 두 벡터의 내적,inner_product의 정규화,normalization된 형태로 계산이 가능하며
코사인유사도,cosine_similarity는 adjacency_matrix 의 열벡터,column_vector 혹은 행벡터,row_vector들을 내적하여 그 값을 비교하는 것
(이하 작성이 안 되어 있음.. 2014년 이후로 update 없음을 보면 앞으로도...)

Lecture 4: Random Network (Erdös-Rényi Network) .... Erdos_Renyi .... https://www.google.com/search?q=Erdös-Rényi
http://sanghyukchun.github.io/50/
이하 세 글은 network_model 관련이며 각각 random_network , small_world_network , scale-free_network 를 다룬다
random_network , random_graph
어떤 고정된 parameter를 갖는 stochastic_model.
표기법은 G(n,p) 인데,
n : vertex 개수
p : 각 vertex pair들이 서로 edge를 가질 independent_probability . // 독립확률 ? 독립성,independence of 확률,probability ... WtEn:independent_probability ?
이 모델은 처음 분석했던 사람들 이름을 따서 Erdos-Renyi_model 이라고도 하며,
그 degree와 edge의 분포,distribution가 푸아송_분포,Poisson_distribution or 베르누이_분포,Bernoulli_distribution를 따르기 때문에
Poisson_random_graph 혹은 Bernoulli_random_graph 라고 하기도 한다.
mean_degree
"한 vertex에서 가지는 평균 edge의 개수"
c로 표기
$\displaystyle c=(n-1)p$
mean_edge
$\displaystyle \binom{n}{k}p$
"평균 edge의 개수는 모든 pair의 개수에서 edge가 존재할 확률인 p를 곱한"
degree_distribution
degree의 분포,distribution
이항분포,binomial_distribution인데, n이 엄청 커지면 푸아송_분포,Poisson_distribution ??? chk
보이는 번역들:
연결선수(degree)의 분포 .... https://ko.wikipedia.org/wiki/척도_없는_네트워크 첫줄
(component에 sub? : )
giant_component
small_component
path_length ... 경로길이,path_length ? 경로,path
average_path_length
n이 아무리 커져도, random_graph 의 diameter ( = longest geodesic distance )가 증가하는 속도는 log n이다. (작다)

Lecture 5: Small world Network (Watts-Strog'z'tz Network) ... Watts-Strogatz 의 오타인듯. .... https://www.google.com/search?q=Watts-Strogztz
http://sanghyukchun.github.io/51/
small_world_network
1998년 발표
random_network 는 실제 네트워크와 맞지 않는 점이 존재. 가장 큰 문제는 degree_distribution 과 clustering_coefficient 가 실제 network와 '반하다'(?) 반한다 - 다르다? 는 점.
regular_network = regular_graph => https://en.wikipedia.org/wiki/Regular_graph https://ko.wikipedia.org/wiki/정규_그래프
는 모든 vertex의 degree가 같다.
k-regular_graph
모든 vertex의 degree가 k이다.
Watts-Strogatz network
2-regular graph를 small_world_network 로 바꾸는 것?
Watts-Strogatz procedure
small_world_network 를 생성하는 방법?
k-regular network에서 임의의 pm(?)개의 edge를 randomly rewire해서 randomness를 주입하는 것이라고.... p가 1~4% (0.01 ~ 0.04) 정도가 되면 small-world effect가 나타난다고.
그리고 저 p값 0.01~0.04 : transition_threshold 혹은 crossover_point 라고 한다.
아무튼 복잡한 수식으로 small world network의 degree sequence distribution을 구한다.
구해보면 푸아송_분포,Poisson_distribution.
엔트로피,entropy ... graph_entropy ?
regular_graph 의 entrpy < random_graph 의 entropy
결론
small world network는 regular network에 확률 p만큼 randomness를 부여해 만들어지는 것.
성질: randomness가 scalable(?), 낮은 entropy(random_network 와 비교해), 놎은 clustering_coefficient and closeness , 짧은 average path와 diameter (그래서 이런 이름?),

Lecture 6: Scale free Network (Barabasi-Albert Network) ... Barabasi-Albert .... https://www.google.com/search?q=Barabasi-Albert
http://sanghyukchun.github.io/52/
scale-free_network
(이건 skip.)
… http://google.com/search?q=power.law vs exponential.law

}


네트워크과학,network_science,netsci Modified on 11:47 am, March 15, 2024.
🎲 Random