🔨 Components of a (Graph)Network
- Object N : Nodes(Vertices)
- Interactions E : Links, Edges
- System G(N,E) : Network, Graph
🔨 Node and Edge Attributes
Possible options
- Weight (ex. frequency of communication)
- Ranking (ex. best friend, second b.f)
- Type (ex. friend, co-worker)
- Sign : Friend vs Foe, Truest vs Distrust
Properties depending on the structure of the rest of the graph
✔️ Undirected vs Directed
✔️ Unweighted vs Weighted
- Weighted : 연결 강도를 Adjacency Matrix에 포함시킬 수 있다.
✔️ Self-edges(self-loops) vs Multigraph
- self-loop나 중복된 link도 Adjacency Matrix에 포함시킬 수 있다
✔️ Bipartite Graph
- 모든 Link가 분리된 Set(U,V) 간에서만 이루어지는 Graph
- 한 쪽 Set만 이용해서 Folded(Projected) Graph를 만들 수도 있다
- Examples : Authors-to-Papers / Actors-to-Movies
🔨Representing Graph
✔️ Adjacency Matric
- Node의 개수가 n일 때, n x n 행렬 A를 만들고, 대응되는 위치의 노드가 연결되어있으면 1, 아니면 0으로 표시한다.
- Undirected의 경우 symmetric(대칭)하다.ㅎ
- 장점 : 연산이 편리하다.
- 단점 : 극도로 sparse(행렬 값이 대부분 0인 경우)하다.
✔️ Edge List
- 2차원 행렬로 Graph 표현
- 장점 : 간단하다
- 단점 : 연산이 불편하여 조작이나 분석이 어렵다
✔️ Adjacency List
- 각 Node의 이웃을 모아서 표현
- Graph가 크거나 Sparse할 때 사용
Reference
https://www.youtube.com/watch?v=JAB_plj2rbA&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=1
