Social Network Analysis (SNA) Part 1

Top'p Kullawattana
Nov 3 · 10 min read

เมื่อผู้เขียน ได้มีโอกาสไปเรียนปริญญาโทที่ภาควิชาวิศวกรรมคอมพิวเตอร์ คณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ก็ได้มีโอกาสไปนั่งเรียน วิชา Social Network Analysis หรือ วิชาที่ว่าด้วยการวิเคราะห์เครือข่ายสังคมออนไลน์ ซึ่งวิชานี้ก็มีความน่าสนใจมากๆ ตรงที่ว่า ได้มีการหยิบยกเรื่องของ “ทฤษฎีกราฟ” มาเป็นพระเอกของวิชานี้ “ถ้าทุกคนยังจำกันได้ ในวิชาแคลคูลัส” ซึ่งจะนำมาใช้ในเรื่องของการวิเคราะห์โครงข่ายของข้อมูล

คำถาม : เก็บไว้ไปตอบกับตัวเอง หลังจากอ่านจบ….

  • การนำ Graph theory มาใช้ในการศึกษาความสัมพันธ์ของข้อมูลในโลกออนไลน์ ข้อมูลที่จะนำมาวิเคราะห์มีเพียงพอหรือเปล่า, น่าสนใจหรือไม่ มีการกระจายตัวของข้อมูลหรือไม่
  • Social Media คือ ???
  • Social Media Mining คือ ???
  • Big Data Paradox ??? — Social Media ถือว่าเป็นข้อมูลขนาดใหญ่
  • การ Representative Data ???
  • Noise Removal Fallacy ???
  • วิธีที่จะ Evaluation Dilemma ???

เริ่มเข้าเนื้อหา…

ในการวิเคราะห์ Social Network เราจะต้องรู้จักกับคำว่า Node และ Edge

จากกราฟนี้ ถ้าเทียบกับการสื่อสารในสังคมออนไลน์ บุคคลจะถูกแสดงด้วยโหนด (วงกลม) และบุคคลที่รู้จักซึ่งกันและกันเชื่อมต่อกับขอบ (เส้น)

A Sample Graph. In this graph, individuals are represented with nodes (circles), and individuals who know each other are connected with edges (lines).
  1. Vertices and Actors
Directed Graph คือ กราฟที่มีความสัมพันธ์แบบมีทิศทางเดียว
Undirected Graph คือ กราฟที่มีความสัมพันธ์ทั้งไปและกลับ

-นิยามของ Node

  • นิยามของ Edge

Note that in Figure Undirected Graph, edges e(v1, v2) and e(v2, v1) are the same edges, because there is no direction in how nodes get connected. We call edges in this graph undirected edges and this kind of graph an undirected graph. Conversely, when edges have directions, e(v1, v2) is not the same as e(v2, v1).

2. Neighborhood

การวิเคราะห์ Degree Distribution

ผลรวมของ degree ใน undirected graph เป็น 2 เท่าของจำนวน edge

ใน directed graph ผลรวมของ in-degrees จะเท่ากับผลรวมของ out-degrees

การวิเคราะห์ Degree Distribution

Example 2.1. For the graph provided in Figure 2.1, the degree distribution pd for d = {1,2,3,4} is

A Sample Graph. In this graph, individuals are represented with nodes (circles), and individuals who know each other are connected with edges (lines).

Because we have four nodes have degree 2, and degrees 1, 3, and 4 are observed once.

3. Power-law Distribution

การวิเคราะห์ Power-law Distribution

As previously discussed, any graph G can be represented as a pair G(V, E), where V is the node set and E is the edge set. Since edges are between nodes, we have

Graphs can also have subgraphs. For any graph G(V, E), a graph G′(V′, E′)

A Graph and Its Corresponding Adjacency Matrix.

is a subgraph of G(V, E), if the following properties hold:

Graph Representation

  • Adjacency Matrix Table
  • Adjacency List (Edge List)

Types of Graphs

  • Null Graph. A null graph is a graph where the node set is empty (there are no nodes). Obviously, since there are no nodes, there are also no edges. Formally,
  • Empty Graph. An empty or edgeless graph is one where the edge set is empty:

4. Signed Edges and Signed Graphs

edge can represent lower social status. Social status is the rank assigned to one’s position in society. For instance, a school principal can be connected via a directed + edge to a student of the school because, in the school environment, the principal is considered to be of higher status. Figure shows a signed graph consisting of nodes and the signed edges between them.

Connectivity in Graphs

  • Adjacent Nodes and Incident Edges.

Adjacent Nodes and Incident Edges. In this graph u and v, as well as v and w, are adjacent nodes, and edges (u, v) and (v, w) are incident edges.

5. Open Walk and Closed Walk

Traversing an Edge. An edge in a graph can be traversed when one starts at one of its end-nodes, moves along the edge, and stops at its other end- node. So, if an edge e(a, b) connects nodes a and b, then visiting e can start at a and end at b. Alternatively, in an undirected graph we can start at b and end the visit at a.

Walk, Path, Trail, Tour, and Cycle. A walk is a sequence of incident edges traversed one after another. In other words, if in a walk one traverses edgese1(v1,v2),e2(v2,v3),e3(v3,v4),…,en(vn,vn+1),we have v1 as the walk’s starting node and vn+1 as the walk’s ending node. When a walk does not end where it started (v1 = vn+1) then it is called an open walk. When a walk returns to where it was started (v1 = vn+1), it is called a closed walk. Similarly, a walk can be denoted as a sequence of nodes, v1, v2, v3, . . . , vn.

In this representation, the edges that are traversed are e1(v1, v2), e2(v2, v3), . . . , en−1(vn−1, vn). The length of a walk is the number of edges traversed during the walk and in our case is n − 1.

Walk, Path, Trail, Tour, and Cycle. In this figure,

  • v4, v3, v6, v4, v2 is a walk
  • v4, v3 is a path
  • v4, v3, v6, v4, v2 is a trail
  • v4, v3, v6, v4 is both a tour and a cycle.

6. Random Walk

Random Walk Algorithm

Connectivity ใน Graph

Components in Undirected และ Directed Graphs

Special Graphs

  • Trees and Forests
A Forest Containing Three Trees

7. Terminal Nodes

Minimum Spanning Tree

Nodes represent cities and values assigned to edges represent geographical distance between cities. High- lighted edges are roads that are built in a way that minimizes their total length.

In a tree with |V| nodes, we have |E| = |V| − 1 edges. This can be proved by contradiction (see Exercises).

Special Subgraphs

Steiner tree for V′ = {v2, v4, v7}

Complete Graphs Ki for 1 ≤ i ≤ 4

Planar and Nonplanar Graphs

Complete Graphs

Bipartite Graphs และ Affiliation Networks

Bipartite Graphs

Regular Graphs

Regular Graph with k = 3

  • Regular graphs can be connected or disconnected. Complete graphs are examples of regular graphs, where all n nodes have degree n − 1 (i.e., k = n − 1). Cycles are also regular graphs, where k = 2. Another example for k = 3

Graph Algorithms

Bridges. Highlighted edges represent bridges; their removal will increase the number of components in the graph.

  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)

Shortest Path Algorithms

  • Dijkstra’s Algorithm

Dijkstra’s Algorithm Execution Example. The shortest path between node s and t is calculated. The values inside nodes at each step show the best shortest path distance computed up to that step. An arrow denotes the node being analyzed.

Minimum Spanning Trees

  • Prim’s Algorithm

8. Source and Sink

Network Flow Algorithms

Commonly, to visualize an edge with capacity c and flow f, we use the notation f /c

Flow Quantity

Example : The flow quantity for the example in Figure is 19:

9. Weak link

  • Ford-Fulkerson Algorithm
  • Augmentation and Augmenting Paths
  • A Flow Network and Its Residual

10. Matching

Maximum Bipartite Matching

  • Augmenting Flow Graph
  • Ford-Fulkerson Algorithm
Maximum Bipartite Matching

can be easily solved by creating a flow graph G(V′, E′, C) from our bipartite graph G(V, E), as follows:

Maximum Bipartite Matching Using Max Flow

11. Cut-Edges

Bridge Detection

สรุป :

  • Actor อาจจะเป็น Type เดียวกันหรือหลาย Type ก็ได้ เช่น USER-USER หรือ USER-PAGE
  • เมื่อหยอด Information ไปในกราฟ ก็จะสามารถเข้าไปถึงบุคคล ๆ นั้น ยกตัวอย่างเช่น เมื่อเรากด like ใน Facebook ของเพื่อนเรา คนที่เป็น mutual friend เราก็จะเห็นเรา
  • เราสามารถส่ง Information ไปหาคนที่เราไม่รู้จักให้เห็นได้
  • การดึงคนไปหนึ่งคนที่อยู่ใน Community ก็จะทำให้ Network เปลี่ยน
  • การทำ Collaborative Filtering เช่น การดูว่าจะ Recommend ใคร จะแนะนำอะไรให้ใครดี ดูจากกราฟ
  • การวิเคราะห์ Similarity คือ การดูความคล้ายกันของข้อมูล
  • เมื่อมีการเก็บข้อมูลมา 1,000,000 คน เราจะแบ่งออกเป็น 900,000 คน นำไป Train Data และอีก 100,000 คนไปทดสอบ
  • การทำ Social Network Analysis ต้องมี Node และ Edge มี Homogeneous (กราฟเนื้อเดียว) กับ Heterogeneous (กราฟเนื้อผสม)
สิ่งที่ควรรู้ และจะต้องนำมาเป็นส่วนหนึ่งในการวิเคราะห์ความสัมพันธ์ของข้อมูล
  • Degree Distribution คือ การหากราฟ Pd = Nd/n
  • กราฟพุ่งเข้า = กราฟพุ่งออก
  • Power Law Distribution คือ จำนวนที่มีเพื่อนในเฟสบุ๊คน้อย ๆ ซึ่งอาจจะมีเยอะ
  • วิธีการแทนกราฟ (Dependency Matrix) คือ การหาจำนวน Degree
  • Sparse Matrix มี Directed กับ Undirected Matrix (คือ อาจจะไปแล้วกลับมาไม่ตรงกันก็ได้)
  • การใส่เป็นคู่ของ Vertex จะอยู่ในรูปแบบ (v1,v2), (v2,v3)
  • Empty graph (คือ กราฟที่เป็น Set ว่าง)
  • กราฟที่มีค่าน้ำหนักไม่เท่ากัน เช่น User คนหนึ่งมีการ มีการ Recommend กับคนเยอะ ๆ
  • Signed Graph กราฟทั้งหมดมีความสำคัญ ในเชิงบวก เชิงลบ มีความเหนือกว่า (User คนนี้มีความเป็นเพื่อนกันหรือเป็นศัตรูกัน)
  • Edge to Edge เชื่อมเข้าด้วยกัน เรียกว่า Incident
  • Walk คือ การเดินต่อๆๆๆๆ กัน เกิดจากการนิยามคำว่า Incident
  • Open Walk คือเดินไปไหนก็ได้
  • Close Walk คือการเดินกลับมาที่จุด Start
  • ความยาวของ Walk คือ จุดที่ไป Visit อาจจะมีการซ้ำกัน
  • Trail คือ walk ที่ไม่มี Edge ใด Edge หนึ่งซ้ำมากกว่าหนึ่งครั้ง และไม่มีโหนดใดที่ถูก Distinct
  • Eulerian คือ ทุก Edge ถูก visit แค่ครั้งเดียว
  • Hamiltonian คือ เป็น Cycle ใด ๆ ที่ถูก Visit โหนดทุกโหนด โดยไม่สนใจ Path
  • Random Walk คือ การสุ่มการเดินตาม Probability

ตัวอย่างการวิเคราะห์ การอ่าน Friend list จาก Web โดยทำแบบ Random Walk โดยให้ความน่าจะเป็นของจำนวนเพื่อน (ถ้ารู้จำนวนเพื่อนและรู้ User)

  • ถ้าไปเลือกการสุ่มจาก Mutual Friend ก็จะมีโอกาสกลับวนหาตัวเองมากขึ้น
  • โหนดใด ๆ จะ Connect จาก Vi — -> Vj
  • Strongly Connected คือ การไปหาทุกโหนดได้ เช่น A — -> B — -> C — -> D หรือ A — -> E หรือ A — -> D (ไม่มีอะไรมา A ได้ เพราะมีแต่พุ่งออก มันควรจะมีการพุ่งเข้า)
  • Weakly Connected คือ โหนดที่สามารถกลับหัวได้ เปลี่ยนทิศ แต่กลับมาจุดเริ่มต้นไม่ได้
  • Diameter: เส้นผ่าศูนย์กลางของกราฟ เท่ากับ Longest กับ Shortest ระหว่าง Node คู่ใด ๆ ที่มีความยาวโหนดมากที่สุด
  • ตัวอย่างเช่น Node รูปดาวจะมี Shortest Node = 1, Longtest Node = 1 เติมโหนดเข้าไปอีก 1 จะเป็น 2
  • Trees and Forests คือ |V| = |E| + 1
  • Node หนึ่ง Node จะมี Edge เฉพาะตัวต่างกัน
  • ถ้า Edge ถูกตัดออกจะได้เป็น Forrest
  • Spanning Tree คือ Tree ที่ใช้ทุก ๆ โหนดในกราฟ เพื่อหา minimum spanning tree คือ การหา tree ที่มี Edge รวมน้อยที่สุด
  • Complete Graphs คือ N = จำนวน Vertex
  • Planar Graphs คือ การหาเส้นตัดของกราฟ
  • Bipartite Graphs เปรียบได้กับ มีเส้นเชื่อมหากัน เช่น User ไป Like Page
  • Regular Graph คือ กราฟมี Edge เท่ากับ K เส้นของ Node
Top'p Kullawattana

Written by

Software Engineer at Kasikorn Business Technology Group (KBTG)

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade