Machine Learning with Graph (2): Components

---

Components of a Network

• Objects: nodes, vertices N
• Interactions: links, edges E
• System: network, graph G(N,E)
• Possible options: Weight, Ranking(최애, 차애), Type(친구, 동료), Sign(friend vs foe, trust vs distrust), Properties depending on the structures of the rest of the graph(Number of common friends)

---

Directed vs Undirected Graphs

---

Representing Graphs

1. Bipartite Graph

A graph whose nodes can be divided into two disjoint sets U and V such that every link connects a node in U to one in V; that is, U and V are independent sets

Example of Folded, Projected  Bipartite graphs; let U be author, V as article. Can make Projections by certain conditions. Such as more than 2 same articles gives connection

2. Adjacency Matrix

Edge List Difficulties in revising or analyzing graph, but still used in deep learning framework

Adjacency List

 

3. More Types of Graphs

---

Connectivity of Directed Graphs

• Strongly/Weakly, Connected/Disconnected, Directed/Undirected
• Strongly connected directed graph vs Weakly connected directed graph
• Strongly connected components (SCCs):

---

Organizing lecture from Stanford CS224W: Machine Learning with Graph (Prof. Jure Leskovec, 2021)
Image Reference: https://snap.stanford.edu/class/cs224w-2021/