Betweeness Centrality

ใช้หาว่าใครเป็นศูนย์กลางระหว่างสองกลุ่ม คำนวนได้จาก

C_b(v_i)=\displaystyle\sum_{s\neq t\neq v_i} \frac{\sigma_{st}(v_i)}{\sigma_{st}}

โดยที่ \sigma_{st} คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t ส่วน  \sigma_{st}(v_i)  คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t แต่ต้องผ่านโหนด v_i

ตัวอย่างfigure_1

จะได้พาททั้งหมดดังนี้

เช่นจะหา C_b(v_2) ทำได้โดย 2\times(\frac{\sigma_{13}(v_2)}{\sigma_{13}}+\frac{\sigma_{14}(v_2)}{\sigma_{14}}+\frac{\sigma_{15}(v_2)}{\sigma_{15}}+\frac{\sigma_{34}(v_2)}{\sigma_{34}}+\frac{\sigma_{35}(v_2)}{\sigma_{35}}+\frac{\sigma_{45}(v_2)}{\sigma_{45}}) สาเหตุที่คูณด้วยสองเพราะว่าเป็นกราฟแบบไม่มีทิศทางดังนั้นจึงมีพาทวิ่งกลับด้วย เช่น จาก 3 ไป 1 จาก 4 ไป 1 จาก 5 ไป 1 เป็นต้น ดังนั้นจะได้

2\sum_{s\neq t \neq v_{i},s<t} \frac{\sigma_{st}(v_i)}{\sigma_{st}}=2\times(\frac{1}{1}+\frac{1}{1}+\frac{2}{2}+\frac{1}{2}+0+0)=7

ถ้าจะเอาไปเทียบกับเครือข่ายสังคมอื่นๆต้อง normalize ก่อน โดยเอาไปหารด้วยค่า max สังเกตจากสมการด้านบนพจน์ที่ 4 หายไปครึ่งหนึ่ง พจน์ที่ 5 กับพจน์ที่ 6 ไม่มี ถ้ามีหมดจะได้ 6 คูณ 2 จะได้ 12  ค่า 12 นี้ก็คือ ทุกพาธจาก s ไป t วิ่งผ่านโหนด 2 หมดซึ่งเป็นค่า max เราเอาค่านี้ไปหาร 7 จะได้ประมาณ 0.5833 จะกล่าวสรุปได้ว่า เมื่อโหนด v_i อยู่ระหว่างเส้นทางที่สั้นที่สุดระหว่าง s กับ t ทุกคู่นั่นคือจะเท่ากับ 1 หรือ \forall(s,t),s\neq t \neq v_{i}\frac{\sigma_{st}(v_i)}{\sigma_{st}}=1 หรือถ้าหาได้ว่าจากโหนด s ไปโหนด t มีกี่คู่ก็ได้ หาได้จากสองเท่าของ combination มี n-1 โหนดเลือก 2 (หรืออีกชื่อไบโนเมียล)2\binom {n-1}{2}=2\times\frac{(n-1)!}{2!((n-1)-2)!}=\frac{(n-1)!}{(n-3)!}=\frac{(n-1)(n-2)(n-3)!}{(n-3)!}=(n-1)(n-2) ดังนั้นจะได้ว่า

C^{norm}_b(v_i)= \frac{C_{b}(v_i)}{2\binom {n-1}{2}} เช่น C^{norm}_b(v_2)= \frac{7}{12}\approx 0.5833

โค้ดโปรแกรม

ผลลัพธ์

สรุป โหนด 2 มีค่า betweeness centrality สูงสุด เป็นตัวเชื่อมระหว่างโหนดต่างๆมากสุด

References
1.Social Media Mining: An Introduction.By Reza Zafarani, Mohammad Ali Abbasi, and Huan Liu.Cambridge University Press, 2014. Draft version: April 20, 2014.
Complete Draft and Slides Available at: http://dmml.asu.edu/smmPage 82-84
2.All shortest Path NetworkX Library at: http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html
3.Betweeness Centrality NetworkX Library at: http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality

Degree Centrality

เป็นการหาว่าโหนดที่เราสนใจมีความสำคัญเพียงใดใน Social Network โดยดูจากจำนวน degree หรือจำนวนเส้นที่เชื่อมต่อระหว่างโหนดที่เราสนใจกับโหนดอื่นๆ สำหรับกราฟไม่มีทิศทาง(undirected graph) ค่า degree centrality C_d สำหรับโหนด v_i คือ
C_d(v_i)=d_i
โดยที่ d_i คือ degree หรือจำนวน adjacent edge ของโหนด v_i
ถ้าเป็นกราฟแบบมีทิศทาง(directed graph) สามารถเลือกใช้ in-degree หรือ out-degree หรือใช้ทั้งสองร่วมกันก็ได้ โดย
C_d(v_i)=d^{in}_i   ใช้วัดว่าบุคคลนั้นเป็นคนที่ได้รับความนิยมเพียงใดใน Social Network
C_d(v_i)=d^{out}_i ใช้วัดว่าบุคคลนั้นเป็นคนที่ชอบเข้าสังคมเพียงใดใน Social Network
แต่ถ้าไม่สนใจทิศทางก็จะได้ C_d(v_i)=d^{in}_i+d^{out}_i ซึ่งจะเท่ากันกับ degree centrality ของกราฟที่ไม่มีทิศทาง

ถ้าจะเอาค่า degree centrality จากเครือข่ายสังคมหนึ่งไปเทียบกับเครือข่ายสังคมอีกอันหนึ่งจะยังเทียบไม่ได้ เช่นเทียบ twitter กับ facebook  ต้องทำการ normalization ก่อนซึ่งทำได้หลายวิธีดังนี้

  1. หารด้วยจำนวน degree ที่เป็นไปได้มากสุด C^{norm}_d(v_i)=\frac{d_i}{n-1} โดยที่ n คือจำนวนโหนด หรือ
  2. หารด้วยจำนวน degree ที่มากที่สุด C^{max}_d(v_i)=\frac{d_i}{max d_j} หรือ
  3. หารด้วยจำนวนผลรวมของ degree C^{sum}_d(v_i)=\frac{d_i}{\sum_{j} d_j}=\frac{d_i}{2|E|}=\frac{d_i}{2m} โดยที่ |E| หรือ m คือจำนวน edge

ตัวอย่างโปรแกรมหา Degree Centrality
figure_1

เป็นกราฟแบบไม่มีทิศทาง บรรทัดแรกที่ปรินท์คือค่าแบบยังไม่ได้ normalize ส่วนค่าบรรทัดต่อมาเป็นค่าเรียงตั้งแต่โหนด 1 – 8 เป็นค่าที่ nomalize แบบ  C^{norm},C^{max},C^{sum} ตามลำดับ

References
1.Social Media Mining: An Introduction.By Reza Zafarani, Mohammad Ali Abbasi, and Huan Liu.Cambridge University Press, 2014. Draft version: April 20, 2014.
Complete Draft and Slides Available at: http://dmml.asu.edu/smm Page 74-75
2.“Social Network Analysis for Startups by Maksim Tsvetovat and Alexander Kouznetsov (O’Reilly). Copyright 2011 Maksim Tsvetovat and Alexander Kouznetsov, 978-1-449-30646-5.” Page 46-48

PageRank Algorithm

อัลกอริทึม PageRank ใช้จัดอันดับเว็บและช่วยให้ได้ผลลัพธ์ของ search engine ที่ดียิ่งขึ้น คิดค้นโดย Sergey Brin และ Larry Page ปี 1998 สมัยเป็นนักศึกษาอยู่ที่ Standford University หรือที่หลายๆท่านรู้จักในฐานะผู้ก่อตั้ง Google หลักการของมันคือ เว็บไซต์จะมีความสำคัญหรือลำดับที่ดีก็ตื่อเมือถูกชี้โดยเหล่าบรรดาเว็บไซต์ที่สำคัญหรือลำดับที่ดีเช่นกัน
ตัวอย่างจากภาพด้านบนเป็น Directed Graph ที่ใช้แทนโครงสร้างของเว็บไซต์
เว็บไซต์เบอร์ 1 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 2 และเว็บไซต์เบอร์ 3เว็บไซต์เบอร์ 2 ไม่มีลิงค์เชื่อมไปยังเว็บไซต์ใดๆเลย
เว็บไซต์เบอร์ 3 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 1 เว็บไซต์เบอร์ 2 และเว็บไซต์เบอร์ 5
เว็บไซต์เบอร์ 4 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 5 และเว็บไซต์เบอร์ 6
เว็บไซต์เบอร์ 5 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 4 และเว็บไซต์เบอร์ 6
เว็บไซต์เบอร์ 6 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 4 เพียบเว็บไซต์เดียว
ปล. หัวลูกศรคือแท่งหนาๆทึบ ไม่ค่อยสวยเท่าไร

ความสำคัญของเว็บไซต์ i เกิดจากผลรวมค่าความสำคัญของเว็บไซต์ใดๆที่ชี้มายังเว็บไซต์ i

  1. เมตริกซ์ H จะใช้เก็บอัตราส่วนค่าของความสำคัญ คำนวณโดย
    H_{i j}=\frac{1}{|P_{i}|}
    |P_{i}| คือจำนวนลิงค์ที่พุ่งออกจากเวอร์เท็กซ์ i
    ถ้ามีลิงค์จากเวอร์เท็กซ์ i ไปเวอร์เท็กซ์ j ถ้าไม่มีลิงค์ให้เป็น 0 ดังนั้นจากกราฟด้านบนจะได้เมตริกซ์ H ดังนี้
    H=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}&0&0&0\\  0&0&0&0&0&0\\  \frac{1}{3}&\frac{1}{3}&0&0&\frac{1}{3}&0\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  0&0&0&\frac{1}{2}&0&\frac{1}{2}\\  0&0&0&1&0&0\\  \end{bmatrix}
    สังเกตได้ว่าถ้ามีลิงค์พุ่งออกมามากอัตราส่วนความสำคัญที่จะกำหนดให้แก่บรรดาเวอร์เท็กซ์ที่ถูกชี้ก็จะถูกทอนให้น้อยลงตามไปด้วยในตอนเริ่มต้นจะให้ทุกๆเวอร์เท็กซ์มีค่าความสำคัญเท่ากัน โดยให้เวกเตอร์  \pi เท่ากับ หนึ่งส่วนด้วยจำนวนเวอร์เท็กซ์ แต่ละเอนทรี่ของเวกเตอร์จะหมายถึงค่าความสำคัญของเวอร์เท็กซ์ที่ 1 ถึง 6 ตามลำดับ เขียนเป็นสมการได้ดังนี้
    \pi^t=\frac{1}{n}=  \begin{bmatrix}^1/_6\;^1/_6\;^1/_6\;^1/_6\;^1/_6\;^1/_6\end{bmatrix}
    โดยที่ n คือจำนวนเวอร์เท็กซ์ สาเหตุที่ต้องทรานสโพสเพราะว่าต้องเอาไปคูณกับเมตริกซ์ H ในขั้นตอนต่อไป
  2. ขั้นตอนต่อมา เราต้องหาก่อนว่า จากเวอร์เท็กซ์ i ไปเวอร์เท็กซ์ j นั้นสามารถทำได้กี่หนทาง อาจจะผ่านเวอร์เท็กซ์อื่นก็ได้ เช่น จากเวอร์เท็กซ์ 3 ไปเวอร์เท็กซ์ 6 ซึ่งจะเดินจาก 3\rightarrow5\rightarrow6 เส้นทางนี้มีความยาว(length)เป็นสอง สิ่งที่เราสนใจคืออัตราส่วนความสำคัญที่เริ่มจากเวอร์เท็กซ์ i ผ่านไปยังเวอร์เท็กซ์ต่างๆจนไปถึงเวอร์เท็กซ์ j ตัวอย่างเช่น 3\rightarrow5\rightarrow6 จะมีอัตราส่วนความสำคัญ ^1/_3\times^1/_2 แล้วเราจะหาอัตราส่วนความสำคัญของการเดินที่มีความยาวเป็น 2 นี้ได้อย่างไร คำตอบคือ การคูณเมตริกซ์ H สองครั้ง หรือ H^2 การคูณเมตริกซ์ระหว่าง H กับ H จะทำให้เกิดการเดินมีความยาวเป็น 2
    H^2=\begin{bmatrix}\frac{1}{6}&\frac{1}{6}&0&0&\frac{1}{6}&0\\  0&0&0&0&0&0\\  0&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&0&\frac{1}{6}\\  0&0&0&\frac{3}{4}&0&\frac{1}{4}\\  0&0&0&\frac{1}{2}&\frac{1}{4}&\frac{1}{4}\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  \end{bmatrix}
    มีเส้นทางดังต่อไปนี้   
    1\rightarrow3\rightarrow 1 =^1/_2\times^1/_3 = ^1/_6
    1\rightarrow3\rightarrow2 =^1/_2\times^1/_3 = ^1/_6
    1\rightarrow3\rightarrow5 =^1/_2\times^1/_3 = ^1/_6
    3\rightarrow1\rightarrow2 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow1\rightarrow3 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow5\rightarrow4 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow5\rightarrow6 =^1/_3\times^1/_2 = ^1/_6
    4\rightarrow5\rightarrow4\&4\rightarrow6\rightarrow4 =^1/_2\times^1/_2 +^1/_2\times1= ^3/_4
    4\rightarrow5\rightarrow6 =^1/_2\times^1/_2 = ^1/_4
    5\rightarrow6\rightarrow4 =1\times^1/_2 = ^1/_2
    5\rightarrow4\rightarrow5 =^1/_2\times^1/_2 = ^1/_4
    5\rightarrow4\rightarrow6 =^1/_2\times^1/_2 = ^1/_4
    6\rightarrow4\rightarrow5 =1\times^1/_2 = ^1/_2
    6\rightarrow4\rightarrow6 =1\times^1/_2 = ^1/_2
    เส้นทางที่ไม่มีทางเดินจะมีค่าอัตราส่วนความสำคัญเป็นศูนย์ ยิ่งถ้าเราเอาเมตริกซ์ H มาคูณด้วยตัวเองเรื่อยๆจะเดินได้ไกลมากขึ้นตัวอย่างเช่น H^3 จะมีเส้นทาง 1\rightarrow3\rightarrow5\rightarrow6 เป็นต้น
  3. ขั้นตอนต่อมาจะเอาเวกเตอร์ค่าความสำคัญ \pi^t คูณกับเมตริกซ์อัตราความสำคัญ H เพื่อดูว่าเมื่อเดินไประยะ lenght=1 นั้นส่งผลต่อเวกเตอร์ค่าความสำคัญ \pi^t แค่ไหน \pi^t_1=\pi^t_0H=\begin{bmatrix}0.056\;0.139\;0.083\;0.250\;0.139\;0.167\end{bmatrix} เมื่อลองรันไปเรื่อยๆจะพบว่า สัก  \pi^t_4=\begin{bmatrix}0.000\;0.000\;0.000\;0.267\;0.133\;0.200\end{bmatrix}  ค่าความสำคัญของเวอร์เท็กซ์ 1 2 และ 3 กลับลดลงจนเข้าใกล้ศูนย์ ทั้งนี้เกิดจากปัญหาสองอย่างคือ
    1. ปัญหา Dangling node เช่นเวอร์เท็กซ์ 2 ซึ่งไม่มีลิงค์ออกจากเวอร์เท็กซ์เลย รับค่าความสำคัญจากเวอร์เท็กซ์ 1 และ 3 เพียงอย่างเดียว ไม่มีการถ่ายโอนไปชี้เวอร์เท็กอื่น ทำให้ค่าความสำคัญของเวอร์เท็กซ์ 2 เป็น 0 ในการลูปครั้งต่อไป วิธีแก้ปัญหาคือเวอร์เท็กซ์ใดเป็น dangling node ให้สร้างลิงค์ไปยังทุกๆเวอร์เทกซ์โดยที่แต่ละลิงค์เท่ากับ \frac{1}{n} หรือเปลี่ยนเมตริกซ์ H เป็นเมตริกซ์ใหม่ที่ชื่อ S ดังนี้
      S=H+a_{i}(\frac{1}{n}e^t)
      โดยที่ a_{i}=1   ก็ต่อเมื่อเวอร์เท็กซ์  i  เป็น dangling node a_{i}=0 เมื่อไม่ใช่ ให้ e^t   คือเวกเตอร์แบบแถวที่เป็น1 หมดมีจำนวนคอลัมน์เท่ากับ n ดังนั้น จะได้
      S=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}&0&0&0\\  \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}\\  \frac{1}{3}&\frac{1}{3}&0&0&\frac{1}{3}&0\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  0&0&0&\frac{1}{2}&0&\frac{1}{2}\\  0&0&0&1&0&0\\  \end{bmatrix}
    2. ปัญหา ก็ยังไม่หมดไปยังมีปัญหาอีกปัญหาคือปัญหา Cycle เช่นเวอร์เท็กซ์ 1 กับเวอร์เท็กซ์ 3 เป็น Cycle วนลูป ทำให้การหาค่าความสำคัญค่อยๆเป็น 0 ในที่สุด และปัญหากราฟไม่เชื่อมต่อกัน Brin และ Page จึงคิดค้น Google Matrix ที่สามารถเทเลพอร์ทไปยังที่อื่นได้ ในกรณีที่ตกอยู่ในวังวนออกมาไม่ได้ ก็จะแรนดอมออกไปยังโครงสร้างเว็บอื่น โดย เมตริกซ์ G คือ
      G=\alpha S+(1-\alpha)\frac{1}{n}e e^t
      โดยที่ \alpha คือค่าสเกล่าร์อยู่ในช่วง 0 ถึง 1
      เช่น \alpha=0.9 หมายถึงจะเดินไปตามโครงสร้างเว็บปรกติ 90% และจะเทเลพอร์ทแบบสุ่มมั่วๆไปหน้าเว็บอื่นๆอีก 10% เราจะเรียก \alpha ว่า damping factor
      และ e e^t เวอร์เตอร์ที่เป็น 1 หมดแบบหลักและแบบแถวคูณกันจะได้เมตริกซ์ขนาด n \times n จะได้
      G=\begin{bmatrix}\frac{1}{60}&\frac{7}{15}&\frac{7}{15}&\frac{1}{60}&\frac{1}{60}&\frac{1}{60}\\  \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}\\  \frac{19}{60}&\frac{19}{60}&\frac{1}{60}&\frac{1}{60}&\frac{19}{60}&\frac{1}{60}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{7}{15}&\frac{7}{15}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{7}{15}&\frac{1}{60}&\frac{7}{15}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{11}{12}&\frac{1}{60}&\frac{1}{60}\\  \end{bmatrix}
      ตัวอย่างการคำนวนเช่น G_{1,2}=\frac{9}{10}\times\frac{1}{2}+\frac{1}{10}\times\frac{1}{6}=\frac{7}{15}
  4.  ใช้เมตริกซ์ G แทนในเมตริกซ์ H ในข้อ 3 ซึ่งจะได้สมการทั่วไปดังนี้
    \pi^t_{k+1}=\pi^t_k G
    ลองรันหลายๆรอบดู \pi^t จะได้เท่ากับ \begin{bmatrix}0.037\;0.054\;0.042\;0.375\;0.206\;0.286\end{bmatrix} หรือลำดับความสำคัญของเวอร์เท็กคือ (6 4 5 1 3 2)

    จากการสังเกตกราฟด้านบนแล้วก็น่าจะจริงที่เวอร์เท็กซ์ 4 มีโอกาสเข้าถึงได้มากกว่าจึงมีความสำคัญอันดับหนึ่ง และอาจเพราะว่าเวอร์เท็กซ์ 6 ชี้มายัง 4 แต่เพียงผู้เดียวด้วยช่วยให้เวอร์เท็กซ์ 4 มีความสำคัญมากขึ้น และเวอร์เทกซ์ 1 2 และ 3 ไม่สามารถเข้าถึงได้โดยเวอร์เทกซ์ 4 5 6 แต่เวอร์เทกซ์ 4 5 6 กลับสามารถูกเข้าถึงโดยเวอร์เทกซ์ 1 2 และ 3 ได้ ทำให้ค่าความสำคัญเวอร์เทกซ์ 4 5 6 มีค่าความสำคัญมากกว่าเวอร์เทกซ์ 1 2 3
    โปรแกรมทั้งหมดสามารถเขียนทดลองใน Microsoft Excel ได้ครับใช้ function คูณเมตริกซ์ MMULT

  5. หรือสามารถทดลองโดยใช้ framework ของเน็ทเวิร์ก networkx

    ผลลัพธ์ {1: 0.03721312715805474, 2: 0.05395936859791858, 3: 0.04150700697389663, 4: 0.3750784815111541, 5: 0.20599776987949375, 6: 0.28624424587948205}
    ตัวโปรแกรมจะลูปโดย default 100 ครั้ง

    โดยปรกติจะใช้ \alpha=0.85

    การประยุกต์ใช้ PageRank กับ Social Network Mining นั้นจะใช้หาว่าบุคคลใดเป็นบุคคลสำคัญที่ถูกอ้างอิงโดยบุคลลอื่นๆที่มีความสำคัญ

    references:
    1. The Mathematics of Web Search http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/
    2.Study of Page Rank Algorithm (slide) http://www.cs.sjsu.edu/faculty/pollett/masters/Semesters/Fall11/tanmayee/Deliverable3.pdf