#noindex 대충, 'network'가 [[그래프,graph]]와 동의어일 수도 있고, (둘 다 vertex(들)이 있고 그것을 잇는 edge(들)까지 포함한 개념) 실제 존재하는 '연결망(network)'을 나타내는 수학적인 수단이나 개념을 [[그래프,graph]]라고 하는 경우도 있고, ... 암튼 단어의 용법이나 사용범위에는 차이가 있으나 대체적으로 graph와 본질적으로 같은 개념. 종종 network을 줄여서 net으로 표현하기도 하고, ... Chkout: WtEn:network WtEn:graph WtEn:net Ggl:"네트워크 그래프 차이" Naver:"네트워크 그래프 차이" ---- Sub: [[Hopfield_network]] =,Hopfield_network . Hopfield_network // 호필드 홉필드 중에? { '''Hopfield network''' 홉필드 네트워크 (aistudy) John_Hopfield http://www.aistudy.com/neural/hopfield_kim.htm (Excerpt from '신경망 이론과 응용, 김대수, 1992') REL [[이징_모형,Ising_model]] [[신경망,neural_network#s-3.1]] WtEn:Hopfield_network WpEn:Hopfield_network ... Ndict:"Hopfield network" Ggl:"Hopfield network" } // Hopfield network [[semantic_network]] - w <> = 네트워크 시각화 network visualization = network_visualization [[시각화,visualization]] 방법이나 sw이나 ... tbw = book: Network Science = by Albert-László Barabási http://networksciencebook.com/ 요약. == Section 2.3 Degree, Average Degree and Degree Distribution == 표기법. Box 2.2 : $\langle x \rangle,\,\langle x^n \rangle$ : see [[적률,moment]] $k$ : degree $k_i$ : node $i$ 의 degree $\langle k \rangle$ : average degree $\langle k \rangle = \frac1N \sum k_i = \frac{2L}{N}$ $k_i = k_i^{in} + k_i^{out}$ (degree = indegree + outdegree) $L$ : total number of links directed network에선 $L=\sum k_i^{in} + \sum k_i^{out}$ $\langle k^{in} \rangle = \langle k^{out} \rangle = \frac{L}{N}$ $N$ : (여기에 명시는 안되어있지만 분명) total number of nodes $N_k$ : degree가 $k$ 인 node의 수 $p$ : probability $p_k$ : 무작위로 뽑은 node의 degree가 $k$ 일 확률 이것은 확률이므로 전체 합이 1이 되도록 정규화되어야 한다. $\sum_{k=1}^{\infty}p_k=1$ $p_k = \frac{N_k}{k}$ $\langle k \rangle$ : average degree of a network $=\sum_{k=0}^{\infty} k p_k$ == Section 2.4 Adjacency Matrix == $A_{ij}=1$ : node j → node i로 가는 link가 있을 때 - ''i → j가 아님에 주의'' $A_{ij}=0$ : 연결이 없을 때 이 책의 [[adjacency_matrix]] convention이 나오는데 이건 책/저자마다 제각각이라 참.. 암튼 행렬과 그래프를 그려야 해서 굿노트로... == Section 2.6 Weighted Networks == [[weighted_network]]의 [[adjacency_matrix]]의 항목의 값은 $A_{ij}=w_{ij}$ Box 2.3 : Metcalfe’s Law: the Value of a Network [[Metcalfe_law]] 네트워크의 값어치? 값? 가치?(value)는 node의 수의 제곱 $N^2$ 에 비례한다는. 이것의 한계점은 * 실제 네트워크들은 대개 sparse. * link의 weight들이 같지 않음. == Section 2.7 Bipartite Networks == 이분그래프? bipartite_graph = bigraph 란, node들이 두개의 [[disjoint_set]]s U and V 로 나뉘고, U끼리는 연결되어 있지 않고, V끼리도 연결되어 있지 않고, link는 U와 V를 잇는 것만 있는 그런 graph. ''rel. [[이분그래프,bipartite_graph]](is a [[그래프,graph]]) [[이분,bipartition]](is a [[분할,partition]])'' 여기에서 U와 V 각각에 대해 projection을 생각할 수 있다. U, V는 set이고, projection U, projection V는 graph이다. U의 두 원소가 V에 의해 매개? 되어 있으면, 그 두 원소를 연결시키는. 그림 보면 쉽게 이해됨. 참조. http://networksciencebook.com/chapter/2/#figure-2-9 ''번역을 뭘로? [[사영,projection]]으로 아님 [[투영,projection]]이나 [[graph_projection]]이라던지 다른걸로? ... Google:graph+projection'' == Section 2.8 Paths and Distances == 네트워크의 { [[경로,path]] [[최단경로,shortest_path]] [[길이,length]] [[거리,distance]] } 등등 mentions: [[경로길이,path_length]] : 쉬움. "A path’s length represents the number of links the path contains" http://networksciencebook.com/chapter/2/#figure-2-12 // [[average_path_length]] 참고로 average path length scales logarithmically with the size of the network: $\langle \ell \rangle \sim \log N$ (Menczer p54) node i, j 사이 [[최단경로,shortest_path]]는 node i, j 사이 [[경로,path]] 중 최소 수의 link를 가진 것. 그래서 그 경로는 BFS breadth-first_search 로 찾음 $d$ : [[거리,distance]] ''(물론 거리는 돌아가는 거리가 아닌 최단거리를 뜻함)'' [[최단경로,shortest_path]] = [[거리,distance]] = [[geodesic_path]] ("The shortest path is often called the distance between nodes i and j") ''(최단경로가 거리? 더 명확하게 최단경로의 [[측도,measure]]나 [[길이,length]]가 거리임을 명시하는게 좋지 않을지?)'' $d_{ij}$ : distance between (a pair of) nodes $i$ and $j$ 물론 [[undirected_network]]=[[undirected_graph]]에서는 $d_{ij}=d_{ji}$ 이고 directed_network에서는 $d_{ij}\ne d_{ji}$ 도 가능. $d_{\rm max}$ : [[지름,diameter]] // [[network_diameter] later? "The longest shortest path in a graph, or the distance between the two furthest nodes" "maximum shortest path in the network" $\langle d \rangle$ : average path length [[순환,cycle]] : start node와 end node가 같은 path. [[오일러_경로,Eulerian_path]] : 각 link를 한번만 traverse하는 path. [[해밀턴_경로,Hamiltonian_path]] : 각 node를 한번만 visit하는 path. == Section 2.9 Connectedness == [[connectedness]] nodes i and j 사이에, connected - path가 존재 disconnected - path does not exist - $d_{ij}=\infty$ network is connected - 모든 node가 connected network is disconnected - $d_{ij}=\infty$ 가 하나라도 존재 == Section 2.10 Clustering Coefficient == [[clustering_coefficient]] [[local_clustering_coefficient]] degree $k_i$ 인 node $i$ 에 대해 the '''local clustering coefficient''' is defined as $C_i = \frac{2L_i}{k_i(k_i-1)$ 여기서 $L_i$ : number of links between the $k_i$ neighbors of node $i$ $0 \le C_i \le 1$ $C_i = 0$ : node $i$ 의 neighbors간의 link가 없음 $C_i = 1$ : node $i$ 의 neighbors가 [[완전그래프,complete_graph]]를 이룸 $C_i$ 는 노드 $i$ 의 이웃들이 서로 연결되어 있을 확률임. 예제 그림 => http://networksciencebook.com/chapter/2/#figure-2-16 [[average_clustering_coefficient]] : $\langle C \rangle$ $\langle C \rangle = \frac1N \sum_{i=1}^N C_i$ == Section 2.13 Advanced Topic 2.A Global Clustering Coefficient == [[global_clustering_coefficient]] $C_{\Delta}$ 혹은 $C_{\triangle}$ ? == Chapter 3 Random Networks == [[random_network]] == Section 3.1 Introduction == 각 node pair가 연결되었을 확률이 $p$ 로 일정한. Box 3.1 G(N,L) model : N개의 labeled nodes가 L개의 randomly placed links로 연결. (Erdős and Rényi) G(N,p) model : 위 설명, 이 책에서 다루는 거 (Gilbert) == Section 3.2 The Random Network Model == == Section 3.3 Number of Links == Box 3.3에서 [[이항분포,binomial_distribution]] 언급 == Section 3.4 Degree Distribution == [[degree_distribution]] [[분포,distribution]] - curr. [[확률분포,probability_distribution]] 특히 두가지 [[이항분포,binomial_distribution]], [[푸아송_분포,Poisson_distribution]] == Section 3.5 Real Networks are Not Poisson == Poisson으로 [[예측,prediction]]한 것(초록색)과 실제(보라색)이 다르다. 그림 => http://networksciencebook.com/chapter/3/#figure-3-6 == Section 3.6 The Evolution of a Random Network == $N_G$ : the size of the largest connected cluster within the network 이것은 $\langle k \rangle$ 와 어떻게 varies할까? 이해가 쉽게 두 extreme cases를 예로 들면 * $p=0$ 이면 $\langle k \rangle = 0$ - 모든 nodes are isolated - largest component의 크기는 $N_G=1$ - 큰 $N$ 에 대해, $N_G/N \to 1$ * $p=1$ 이면 $\langle k \rangle = N-1$ - network는 완전그래프 - 모든 nodes는 belong to a single component - $N_G=N$ - $N_G/N=1$ $\langle k \rangle$ 가 $0$ 에서 $N-1$ 까지 증가하면, $N_G$ 가 $1$ 에서 $N$ 까지 점진적으로 증가하지 않는다. 처음에는 작은 $\langle k \rangle$ 에 대해서는 $N_G/N$ 은 0이다. 그런데 critical value를 넘으면 'giant component'라 부르는 큰 덩이(large cluster)가 빠른 속도로 나타난다. 이것의 출현(emergence) 조건은 $\langle k \rangle=1$ 이다. 여기에 식 (3.3) $\langle k \rangle= \frac{2\langle L \rangle}{N}=p(N-1)$ 를 적용하면 (average degree of a random network) $p_c = \frac1{N-1} \approx \frac1N$ [[임계점,critical_point]]은 $\langle k \rangle = 1 \; (p = 1/N)$ (그림에서 c) 이고 regime을 나누는데, subcritical regime : 임계점 왼쪽 (그림에서 b) $0 < \langle k \rangle < 1 \; (p < 1/N)$ supercritical regime : 임계점 오른쪽 (그림에서 d) $0 < \langle k \rangle > 1 \; (p > 1/N)$ connected regime : 더 나아간 (그림에서 e) $0 < \langle k \rangle > \ln N \; (p > \ln N/N)$ 그림 => http://networksciencebook.com/chapter/3/#figure-3-7 == Section 3.7 Real Networks are Supercritical == subcritical ↔ supercritical ↔ fully connected 이 사이에서, 대개의 real network는 supercritical. [[subcritical_network]] [[supercritical_network]] == Section 3.8 Small Worlds == [[small_world]] [[small_world_network]] [[small-world_network]] (pagename TBD) small world phenomenon = six degrees of separation == Section 3.9 Clustering Coefficient == [[clustering_coefficient]] == Section 3.10 Summary: Real Networks are Not Random == == Chapter 4 The Scale-Free Property == [[scale_free_network]] or [[scale-free_network]] pagename TBD == Section 4.1 Introduction == == Section 4.2 Power Laws and Scale-Free Networks == $p_k \sim k^{-\gamma}$ $\log p_k \sim -\gamma \log k$ == Section 4.3 Hubs == == Section 4.4 The Meaning of Scale-Free == == Section 4.5 Universality == == Section 4.6 Ultra-Small Property == == Section 4.7 The Role of the Degree Exponent == == Section 4.8 Generating Networks with Arbitrary Degree Distribution == [[configuration_model]] [[degree-preserving_randomization]] [[hidden_parameter_model]] == Section 4.9 Summary == == Chapter 5 The Barabási-Albert Model == [[Barabasi-Albert]] [[WpEn:Barabási–Albert_model]] == Section 5.1 Introduction == == Section 5.2 Growth and Preferential Attachment == == Section 5.3 The Barabási-Albert Model == [[preferential_attachment]] new node의 link가 node $i$ 에 연결(connect)하는 것이 degree $k_i$ 에 의존할 확률 $\Pi(k)$ $\Pi(k_i) = \frac{ k_i }{ \sum_j k_j }$ == Section 5.4 Degree Dynamics == == Section 5.5 Degree Distribution == [[degree_distribution]] [[continuum_theory]] (Box 5.3) == Section 5.6 The Absence of Growth or Preferential Attachment == == Section 5.7 Measuring Preferential Attachment == == Section 5.8 Non-linear Preferential Attachment == Sublinear Preferential Attachment (0 < α < 1) Superlinear Preferential Attachment (α > 1) [[선형성,linearity]] and [[비선형성,nonlinearity]] == Section 5.9 The Origins of Preferential Attachment == == Section 5.10 Diameter and Clustering Coefficient == [[network_diameter]] mklink [[clustering_coefficient]] (section 3.9) == Chapter 6 Evolving Networks == == Section 6.1 Introduction == == Section 6.2 The Bianconi-Barabási Model == == Section 6.3 Measuring Fitness == == Section 6.4 Bose-Einstein Condensation == == Section 6.5 Evolving Networks == == Section 6.6 Summary == == Chapter 7 Degree Correlations == == Section 7.1 Introduction == == Section 7.2 Assortativity and Disassortativity == == Section 7.3 Measuring Degree Correlations == Box 7.1 - [[friendship_paradox]] Box 7.2 - [[degree_correlation_coefficient]] == Section 7.4 Structural Cutoffs == == Section 7.5 Correlations in Real Networks == == Section 7.6 Generating Correlated Networks == == Section 7.7 The Impact of Degree Correlations == == Section 7.8 Summary == == Chapter 8 Network Robustness == == Section 8.1 Introduction == == Section 8.2 Percolation Theory == [[percolation]] [[percolation_theory]] == Section 8.3 Robustness of Scale-free Networks == == Section 8.4 Attack Tolerance == == Section 8.5 Cascading Failures == == Section 8.6 Modeling Cascading Failures == * Failure Propagation Model * Branching Model == Section 8.7 Building Robustness == [[robustness]] [[robust_network]] == Section 8.8 Summary: Achilles' Heel == == Chapter 9 Communities == [[community]] == Section 9.1 Introduction == == Section 9.2 Basics of Communities == Box 9.1 - [[graph_partitioning]] ([[그래프,graph]] [[분할,partition]]), [[Kernighan-Lin_algorithm]] [[community_detection]] == Section 9.3 Hierarchical Clustering == [[hierarchical_clustering]] { [[위계,hierarchy]] [[clustering]] } [[Ravasz_algorithm]] - [[similarity_matrix]] { [[유사도,similarity]] [[행렬,matrix]] } 를 먼저 정의함. [[Girvan-Newman_algorithm]] == Section 9.4 Modularity == [[modularity]] [[module]] == Section 9.5 Overlapping Communities == [[clique_percolation]] { [[클릭,clique]] } [[link_clustering]] == Section 9.6 Testing Communities == == Section 9.7 Characterizing Communities == == Chapter 10 Spreading Phenomena == http://networksciencebook.com/chapter/10 == Section 10.1 Introduction == == Section 10.2 Epidemic Modeling == Susceptible-Infected (SI) Model SI_model Susceptible-Infected-Susceptible (SIS) Model SIS_model Susceptible-Infected-Recovered (SIR) Model SIR_model == Section 10.3 Network Epidemics == == Section 10.4 Contact Networks == == Section 10.5 Beyond the Degree Distribution == [[temporal_network]] [[aggregated_network]] == Section 10.8 Summary == = bmks ko = https://mons1220.tistory.com/category/공부/네트워크과학 https://blog.naver.com/sw4r - 네트워크 category https://blog.naver.com/sw4r/221218195084 - Complex Network 43개의 글 - 중 첫 글 https://blog.naver.com/sw4r/221232749977 - Complexity 84개의 글 - 중 첫 글 [[그래프이론,graph_theory]]에서 말하는 [[그래프,graph]]의 일종인 '''network''': https://proofwiki.org/wiki/Definition:Network ---- Twin RR : 네트워크,network