대충,
'network'가
그래프,graph와 동의어일 수도 있고, (둘 다 vertex(들)이 있고 그것을 잇는 edge(들)까지 포함한 개념)
실제 존재하는 '연결망(network)'을 나타내는 수학적인 수단이나 개념을
그래프,graph라고 하는 경우도 있고, ...
암튼 단어의 용법이나 사용범위에는 차이가 있으나 대체적으로 graph와 본질적으로 같은 개념.
종종 network을 줄여서 net으로 표현하기도 하고, ...
1. 네트워크 시각화 network visualization ¶
2. book: Network Science ¶
2.1. Section 2.3 Degree, Average Degree and Degree Distribution ¶
표기법.
: degree
: node
의 degree
: average degree
(degree = indegree + outdegree)
: total number of links
directed network에선
: (여기에 명시는 안되어있지만 분명) total number of nodes
: degree가
인 node의 수
: probability
: 무작위로 뽑은 node의 degree가
일 확률
이것은 확률이므로 전체 합이 1이 되도록 정규화되어야 한다.
: average degree of a network
2.2. Section 2.4 Adjacency Matrix ¶
: node j → node i로 가는 link가 있을 때 -
i → j가 아님에 주의
: 연결이 없을 때
이 책의
adjacency_matrix convention이 나오는데 이건 책/저자마다 제각각이라 참..
암튼 행렬과 그래프를 그려야 해서 굿노트로...
2.3. Section 2.6 Weighted Networks ¶
2.4. Section 2.7 Bipartite Networks ¶
2.5. Section 2.8 Paths and Distances ¶
//
average_path_length
참고로 average path length scales logarithmically with the size of the network:
(Menczer p54)
:
지름,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"
: average path length
순환,cycle : start node와 end node가 같은 path.
2.6. Section 2.9 Connectedness ¶
nodes i and j 사이에,
connected - path가 존재
disconnected - path does not exist -
network is connected - 모든 node가 connected
network is disconnected -
가 하나라도 존재
2.7. Section 2.10 Clustering Coefficient ¶
local_clustering_coefficient
degree
인 node
에 대해 the
local clustering coefficient is defined as
여기서
: number of links between the
neighbors of node
: node
의 neighbors간의 link가 없음
: node
의 neighbors가
완전그래프,complete_graph를 이룸
는 노드
의 이웃들이 서로 연결되어 있을 확률임.
2.8. Section 2.13 Advanced Topic 2.A Global Clustering Coefficient ¶
혹은
?
2.9. Chapter 3 Random Networks ¶
2.10. Section 3.1 Introduction ¶
각 node pair가 연결되었을 확률이
로 일정한.
Box 3.1
G(N,L) model : N개의 labeled nodes가 L개의 randomly placed links로 연결. (Erdős and Rényi)
G(N,p) model : 위 설명, 이 책에서 다루는 거 (Gilbert)
2.11. Section 3.2 The Random Network Model ¶
2.12. Section 3.3 Number of Links ¶
2.13. Section 3.4 Degree Distribution ¶
2.14. Section 3.5 Real Networks are Not Poisson ¶
2.15. Section 3.6 The Evolution of a Random Network ¶
: the size of the largest connected cluster within the network
이것은
와 어떻게 varies할까?
이해가 쉽게 두 extreme cases를 예로 들면
- 이면
- 모든 nodes are isolated
- largest component의 크기는
- 큰
에 대해,
- 이면
- network는 완전그래프
- 모든 nodes는 belong to a single component
-
-
가
에서
까지 증가하면,
가
에서
까지 점진적으로 증가하지 않는다.
처음에는 작은
에 대해서는
은 0이다. 그런데 critical value를 넘으면 'giant component'라 부르는 큰 덩이(large cluster)가 빠른 속도로 나타난다. 이것의 출현(emergence) 조건은
이다. 여기에 식 (3.3)
를 적용하면 (average degree of a random network)
임계점,critical_point은
(그림에서 c)
이고 regime을 나누는데,
subcritical regime : 임계점 왼쪽 (그림에서 b)
supercritical regime : 임계점 오른쪽 (그림에서 d)
connected regime : 더 나아간 (그림에서 e)
그림 =>
http://networksciencebook.com/chapter/3/#figure-3-7
2.16. Section 3.7 Real Networks are Supercritical ¶
subcritical ↔ supercritical ↔ fully connected
이 사이에서, 대개의 real network는 supercritical.
2.17. Section 3.8 Small Worlds ¶
small world phenomenon = six degrees of separation
2.18. Section 3.9 Clustering Coefficient ¶
2.19. Section 3.10 Summary: Real Networks are Not Random ¶
2.20. Chapter 4 The Scale-Free Property ¶
2.21. Section 4.1 Introduction ¶
2.22. Section 4.2 Power Laws and Scale-Free Networks ¶
2.24. Section 4.4 The Meaning of Scale-Free ¶
2.25. Section 4.5 Universality ¶
2.26. Section 4.6 Ultra-Small Property ¶
2.27. Section 4.7 The Role of the Degree Exponent ¶
2.28. Section 4.8 Generating Networks with Arbitrary Degree Distribution ¶
2.30. Chapter 5 The Barabási-Albert Model ¶
2.31. Section 5.1 Introduction ¶
2.32. Section 5.2 Growth and Preferential Attachment ¶
2.33. Section 5.3 The Barabási-Albert Model ¶
new node의 link가 node
에 연결(connect)하는 것이 degree
에 의존할 확률
2.34. Section 5.4 Degree Dynamics ¶
2.35. Section 5.5 Degree Distribution ¶
2.36. Section 5.6 The Absence of Growth or Preferential Attachment ¶
2.37. Section 5.7 Measuring Preferential Attachment ¶
2.38. Section 5.8 Non-linear Preferential Attachment ¶
Sublinear Preferential Attachment (0 < α < 1)
Superlinear Preferential Attachment (α > 1)
2.39. Section 5.9 The Origins of Preferential Attachment ¶
2.40. Section 5.10 Diameter and Clustering Coefficient ¶
2.41. Chapter 6 Evolving Networks ¶
2.42. Section 6.1 Introduction ¶
2.43. Section 6.2 The Bianconi-Barabási Model ¶
2.44. Section 6.3 Measuring Fitness ¶
2.45. Section 6.4 Bose-Einstein Condensation ¶
2.46. Section 6.5 Evolving Networks ¶
2.48. Chapter 7 Degree Correlations ¶
2.49. Section 7.1 Introduction ¶
2.50. Section 7.2 Assortativity and Disassortativity ¶
2.51. Section 7.3 Measuring Degree Correlations ¶
2.52. Section 7.4 Structural Cutoffs ¶
2.53. Section 7.5 Correlations in Real Networks ¶
2.54. Section 7.6 Generating Correlated Networks ¶
2.55. Section 7.7 The Impact of Degree Correlations ¶
2.57. Chapter 8 Network Robustness ¶
2.58. Section 8.1 Introduction ¶
2.59. Section 8.2 Percolation Theory ¶
2.60. Section 8.3 Robustness of Scale-free Networks ¶
2.61. Section 8.4 Attack Tolerance ¶
2.62. Section 8.5 Cascading Failures ¶
2.63. Section 8.6 Modeling Cascading Failures ¶
- Failure Propagation Model
- Branching Model
2.64. Section 8.7 Building Robustness ¶
2.65. Section 8.8 Summary: Achilles' Heel ¶
2.67. Section 9.1 Introduction ¶
2.68. Section 9.2 Basics of Communities ¶
2.69. Section 9.3 Hierarchical Clustering ¶
2.70. Section 9.4 Modularity ¶
2.71. Section 9.5 Overlapping Communities ¶
2.72. Section 9.6 Testing Communities ¶
2.73. Section 9.7 Characterizing Communities ¶
2.74. Chapter 10 Spreading Phenomena ¶
2.75. Section 10.1 Introduction ¶
2.76. 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
2.77. Section 10.3 Network Epidemics ¶
2.78. Section 10.4 Contact Networks ¶
2.79. Section 10.5 Beyond the Degree Distribution ¶