Betweeness Centrality

ใช้หาว่าใครเป็นศูนย์กลางระหว่างสองกลุ่ม คำนวนได้จาก โดยที่ คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t ส่วน   คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t แต่ต้องผ่านโหนด  ตัวอย่าง

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

เช่นจะหา  ทำได้โดย  สาเหตุที่คูณด้วยสองเพราะว่าเป็นกราฟแบบไม่มีทิศทางดังนั้นจึงมีพาทวิ่งกลับด้วย เช่น จาก 3 ไป 1 จาก 4 ไป 1 จาก 5 ไป 1 เป็นต้น ดังนั้นจะได้ ถ้าจะเอาไปเทียบกับเครือข่ายสังคมอื่นๆต้อง normalize ก่อน โดยเอาไปหารด้วยค่า max สังเกตจากสมการด้านบนพจน์ที่ 4 หายไปครึ่งหนึ่ง พจน์ที่ 5 กับพจน์ที่ 6 ไม่มี ถ้ามีหมดจะได้ 6 คูณ 2 จะได้ 12  ค่า 12 นี้ก็คือ…

Degree Centrality

เป็นการหาว่าโหนดที่เราสนใจมีความสำคัญเพียงใดใน Social Network โดยดูจากจำนวน degree หรือจำนวนเส้นที่เชื่อมต่อระหว่างโหนดที่เราสนใจกับโหนดอื่นๆ สำหรับกราฟไม่มีทิศทาง(undirected graph) ค่า degree centrality สำหรับโหนด  คือ โดยที่  คือ degree หรือจำนวน adjacent edge ของโหนด  ถ้าเป็นกราฟแบบมีทิศทาง(directed graph) สามารถเลือกใช้ in-degree หรือ out-degree หรือใช้ทั้งสองร่วมกันก็ได้ โดย   ใช้วัดว่าบุคคลนั้นเป็นคนที่ได้รับความนิยมเพียงใดใน Social Network  ใช้วัดว่าบุคคลนั้นเป็นคนที่ชอบเข้าสังคมเพียงใดใน Social Network แต่ถ้าไม่สนใจทิศทางก็จะได้ ซึ่งจะเท่ากันกับ degree centrality ของกราฟที่ไม่มีทิศทาง ถ้าจะเอาค่า degree centrality จากเครือข่ายสังคมหนึ่งไปเทียบกับเครือข่ายสังคมอีกอันหนึ่งจะยังเทียบไม่ได้ เช่นเทียบ twitter กับ facebook  ต้องทำการ normalization ก่อนซึ่งทำได้หลายวิธีดังนี้ หารด้วยจำนวน degree ที่เป็นไปได้มากสุด  โดยที่ n…

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…