Skip to content
กลับไปยังผลการค้นหา

Eigenvector Centrality

ผู้เสนอ
Bonacich, P.
ปี
1972
ประเภท
Centrality measure
กลุ่มวิธี
Network science

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Eigenvector centrality ซึ่ง Bonacich นำเสนอในปี 1972 เป็นการวัดอิทธิพลของโหนดโดยพิจารณาไม่เพียงแค่จำนวนเพื่อนบ้านที่มี แต่ยังรวมถึงอิทธิพลของเพื่อนบ้านเหล่านั้นด้วย โหนดจะได้คะแนนสูงหากเชื่อมต่อกับโหนดอื่นที่มีคะแนนสูง ทำให้เป็นมาตรวัดความสำคัญเชิงโครงสร้างในเครือข่ายที่มีลักษณะเวียนเกิดและรับรู้ถึงภาพรวม

แนวคิดเบื้องหลังวิธีการ

การมีการเชื่อมโยงที่ดีเป็นสิ่งสำคัญ แต่การเชื่อมโยงกับผู้ที่มีการเชื่อมโยงที่ดีนั้นสำคัญยิ่งกว่า Eigenvector centrality รวบรวมแนวคิดแบบเวียนเกิดนี้: คะแนนของคุณขึ้นอยู่กับคะแนนของเพื่อนบ้าน ซึ่งจะขึ้นอยู่กับคะแนนของเพื่อนบ้านของเพื่อนบ้าน และดำเนินไปเรื่อย ๆ ทั่วทั้งเครือข่าย เสมือนว่าอิทธิพลไหลเวียนอย่างต่อเนื่องทั่วทั้งเครือข่ายจนกระทั่งถึงจุดสมดุลที่เสถียร ซึ่งก็คือ eigenvector หลักของเมทริกซ์ประชิด โดยที่คะแนนของแต่ละโหนดเป็นสัดส่วนกับผลรวมของคะแนนเพื่อนบ้าน

ประวัติศาสตร์

Eigenvector centrality ได้รับการกำหนดอย่างเป็นทางการโดย Phillip Bonacich ในบทความปี 1972 เกี่ยวกับแนวทางการแยกตัวประกอบและการถ่วงน้ำหนักสำหรับคะแนนสถานะ ซึ่งเป็นการวางรากฐานทางทฤษฎีสำหรับมาตรวัด centrality ที่อิงตามศักดิ์ศรี แนวคิดที่ว่าความสำคัญของโหนดเป็นสัดส่วนกับผลรวมของความสำคัญของเพื่อนบ้านมีมาก่อน Bonacich ในแนวคิดทางสังคมวิทยาของสถานะ แต่การกำหนดอย่างเป็นทางการเชิงพีชคณิตของเขาทำให้สามารถคำนวณได้ มาตรวัดนี้ได้รับการยอมรับอย่างกว้างขวางในการวิเคราะห์เครือข่ายสังคม และต่อมาในบรรณานุกรมศาสตร์และการวิเคราะห์กราฟเว็บ ซึ่งเป็นแรงบันดาลใจโดยตรงให้กับอัลกอริทึม PageRank ของ Google (1998) ซึ่งเพิ่มปัจจัยการหน่วงเพื่อจัดการกับกราฟที่มีทิศทางและไม่เชื่อมต่อกัน

ควรใช้เมื่อใด

ใช้ eigenvector centrality เมื่อคุณต้องการระบุโหนดที่มีอิทธิพลไม่เพียงเพราะมีจำนวนการเชื่อมต่อมาก แต่เพราะโหนดเหล่านั้นฝังตัวอยู่ในพื้นที่ที่มีการเชื่อมต่อหนาแน่นและมีสถานะสูงในเครือข่าย ซึ่งเป็นเรื่องปกติในเครือข่ายการอ้างอิง งานวิจัยอิทธิพลทางสังคม และการวิเคราะห์ศักดิ์ศรีองค์กร เหมาะสำหรับเครือข่ายแบบไม่มีทิศทางหรือเครือข่ายแบบมีทิศทางสมมาตรที่แนวคิดของการเสริมแรงร่วมกันมีความหมายในทางปฏิบัติ หลีกเลี่ยงการใช้กับกราฟที่ไม่เชื่อมต่อกัน (คะแนนจะไม่มีความหมายสำหรับองค์ประกอบที่แยกตัว) กับกราฟอะไซคลิกแบบมีทิศทาง (leading eigenvector จะเสื่อมสภาพ) หรือเมื่อคำถามวิจัยเป็นเรื่องของการเชื่อมต่อในท้องถิ่นมากกว่าศักดิ์ศรีโดยรวม สำหรับเครือข่ายแบบมีทิศทางที่มีอิทธิพลแบบไม่สมมาตร PageRank โดยทั่วไปจะดีกว่า

ข้อจำกัดและข้อควรพิจารณา

  • ไม่มีความหมายหรือเสื่อมสภาพในกราฟที่ไม่เชื่อมต่อกันและกราฟอะไซคลิกแบบมีทิศทาง ซึ่ง leading eigenvector ไม่ให้คะแนนที่มีความหมายสำหรับทุกโหนด
  • อ่อนไหวต่อความหนาแน่นและโครงสร้างของเครือข่าย: ในเครือข่ายที่เบาบางมาก โหนดเกือบทั้งหมดจะมีคะแนนใกล้ศูนย์ ยกเว้นฮับขนาดเล็ก
  • ไม่พิจารณาความยาวของเส้นทางหรือบทบาทการเชื่อมโยง; โหนดที่เชื่อมต่อสองกลุ่มที่หนาแน่นอาจได้คะแนนต่ำแม้จะมีความสำคัญเชิงโครงสร้าง
  • สำหรับเครือข่ายแบบมีทิศทางที่ไม่สมมาตร มาตรวัดนี้ต้องมีการปรับเปลี่ยน (เช่น PageRank) และการนำไปใช้แบบตรงไปตรงมาอาจทำให้เข้าใจผิดได้

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • จับภาพอิทธิพลแบบเวียนเกิดและภาพรวม แทนที่จะเป็นเพียงระดับท้องถิ่น เผยให้เห็นศักดิ์ศรีและความสำคัญเชิงโครงสร้างพร้อมกัน
  • มีพื้นฐานมาจากกรอบพีชคณิตเชิงเส้นที่เป็นหลักการ โดยมีผลเฉลยที่ไม่ซ้ำกันซึ่งรับประกันโดยทฤษฎีบท Perron-Frobenius สำหรับเครือข่ายที่เชื่อมต่อกัน
  • พิจารณาคุณภาพของการเชื่อมต่ออย่างเป็นธรรมชาติ ไม่ใช่แค่ปริมาณ ทำให้เหมาะสำหรับการวิจัยศักดิ์ศรีและสถานะ
  • คำนวณได้อย่างมีประสิทธิภาพผ่าน power iteration แม้ในเครือข่ายขนาดใหญ่ที่มีความเบาบาง
  • ตีความได้โดยตรง: คะแนนสะท้อนถึงอิทธิพลตามสัดส่วนเมื่อเทียบกับโหนดที่เป็นศูนย์กลางมากที่สุด

การประยุกต์ใช้

  • การระบุศักดิ์ศรีและอิทธิพลในเครือข่ายการอ้างอิงทางวิชาการและกราฟการเขียนร่วม
  • การทำแผนที่โครงสร้างอำนาจและผู้นำทางความคิดในเครือข่ายองค์กรและการเมือง
  • การตรวจจับโหนดฮับในเครือข่ายปฏิสัมพันธ์โปรตีนทางชีวภาพและเครือข่ายควบคุมยีน
  • การจัดอันดับหน้าเว็บและเอกสารตามอำนาจเชิงโครงสร้าง (เป็นรากฐานของ PageRank)
  • การวิเคราะห์การแพร่กระจายอิทธิพลและผู้เผยแพร่หลักในเครือข่ายโซเชียลมีเดีย
  • การประเมินลำดับชั้นสถานะในการศึกษาเครือข่ายสังคมวิทยาและมิตรภาพ

วิธีการทำงาน

วิธีการทำงาน

1

เครือข่ายจะถูกแทนด้วยเมทริกซ์ประชิด A โดยที่ค่า A_ij เท่ากับ 1 (หรือค่าน้ำหนักของเส้นเชื่อมสำหรับเครือข่ายถ่วงน้ำหนัก) หากโหนด i และ j เชื่อมต่อกัน และเท่ากับ 0 หากไม่เชื่อมต่อกัน เมทริกซ์นี้เข้ารหัสโครงสร้างการเชื่อมต่อทั้งหมดที่จะใช้ในการคำนวณค่า centrality

2

ค่า eigenvalue ที่ใหญ่ที่สุดและ eigenvector ที่เกี่ยวข้องจะถูกคำนวณจากเมทริกซ์ประชิดโดยใช้วิธี power iteration หรือตัวแก้สมการพีชคณิตเชิงเส้นมาตรฐาน ค่า eigenvalue หลัก lambda_max รับประกันว่าเป็นจำนวนจริงและเป็นบวกสำหรับเครือข่ายที่เชื่อมต่อกันตามทฤษฎีบท Perron-Frobenius ซึ่งทำให้มั่นใจได้ว่ามีผลเฉลยที่ไม่ซ้ำกันและตีความได้

สูตร
\mathbf{A}\mathbf{x} = \lambda_{\max}\mathbf{x}
3

แต่ละโหนดจะได้รับองค์ประกอบที่สอดคล้องกันของ eigenvector หลักเป็นคะแนน centrality คะแนนนี้เป็นไปตามเงื่อนไขจุดตรึง (fixed-point condition): คะแนนของโหนดเท่ากับ (1/lambda_max) คูณผลรวมของคะแนนเพื่อนบ้าน ดังนั้นโหนดที่มีคะแนนสูงจะดึงคะแนนของเพื่อนบ้านให้สูงขึ้นแบบเวียนเกิด

สูตร
x_i = \frac{1}{\lambda_{\max}} \sum_{j \in N(i)} x_j
4

โดยทั่วไปแล้ว คะแนนจะถูกปรับขนาดเพื่อให้ค่าสูงสุดเท่ากับ 1 ทำให้สามารถเปรียบเทียบกันได้ระหว่างเครือข่ายที่มีขนาดต่างกัน การจัดอันดับสัมพัทธ์ของโหนดจะยังคงอยู่ไม่ว่าจะใช้การปรับค่ามาตรฐานแบบใด

ข้อผิดพลาดที่พบบ่อย

  • การใช้ eigenvector centrality กับเครือข่ายที่ไม่เชื่อมต่อกันโดยไม่ได้แยกองค์ประกอบที่เชื่อมต่อกันที่ใหญ่ที่สุดออกมาก่อน ซึ่งนำไปสู่คะแนนศูนย์สำหรับกราฟย่อยทั้งหมด
  • การสับสนระหว่าง eigenvector centrality กับ degree centrality และการไม่รายงานว่าใช้มาตรวัดใด; ทั้งสองสามารถให้การจัดอันดับที่แตกต่างกันมาก
  • การใช้กับเครือข่ายแบบมีทิศทางโดยไม่ตรวจสอบว่ากราฟมีการเชื่อมต่ออย่างแน่นหนา (strongly connected) หรือปรับให้เข้ากับรูปแบบที่มีทิศทาง เช่น PageRank
  • การถือว่าความแตกต่างเล็กน้อยในคะแนนที่ปรับค่ามาตรฐานแล้วมีความหมาย ในขณะที่เครือข่ายมีความเบาบางและคะแนนถูกบีบอัดเชิงตัวเลขใกล้ศูนย์
  • การละเว้นการตรวจสอบความอ่อนไหว: การจัดอันดับ centrality สามารถเปลี่ยนแปลงได้อย่างมากหากมีการลบโหนดฮับที่มีดีกรีสูงออกไปไม่กี่โหนด

คำถามที่พบบ่อย

eigenvector centrality แตกต่างจาก degree centrality อย่างไร?

Degree centrality นับเฉพาะเพื่อนบ้านที่อยู่ติดกัน โดยถือว่าการเชื่อมต่อทั้งหมดเท่ากัน Eigenvector centrality ถ่วงน้ำหนักเพื่อนบ้านแต่ละรายด้วยค่า centrality ของเพื่อนบ้านนั้นเอง ดังนั้นการเชื่อมต่อกับโหนดที่มี centrality สูงจึงมีส่วนสำคัญมากกว่าการเชื่อมต่อกับโหนดรอบนอก โหนดที่มีเพื่อนบ้านน้อยแต่มีอิทธิพลมากสามารถจัดอันดับสูงกว่าโหนดที่มีดีกรีสูงซึ่งเชื่อมต่อกับโหนดรอบนอกเป็นส่วนใหญ่

เหตุใด eigenvector centrality จึงล้มเหลวในกราฟอะไซคลิกแบบมีทิศทาง?

ในกราฟอะไซคลิกแบบมีทิศทางจะไม่มีวงจร ดังนั้นอิทธิพลจึงไม่สามารถไหลย้อนกลับได้ Eigenvector หลักของเมทริกซ์ประชิดจะกำหนดคะแนนศูนย์ให้กับโหนดทั้งหมด ยกเว้นโหนดที่ไม่มีเส้นเชื่อมขาออก (sinks) ทำให้มาตรวัดเสื่อมสภาพ PageRank แก้ปัญหานี้โดยการเพิ่มเทอมการเคลื่อนย้าย (teleportation term) ที่กระจายน้ำหนักอย่างสม่ำเสมอ

ฉันสามารถใช้ eigenvector centrality กับเครือข่ายถ่วงน้ำหนักได้หรือไม่?

ได้ แทนที่เมทริกซ์ประชิดแบบไบนารีด้วยเมทริกซ์ประชิดแบบถ่วงน้ำหนักและใช้การแยกองค์ประกอบหลัก (eigen-decomposition) แบบเดียวกัน จากนั้น eigenvector หลักจะสะท้อนทั้งจำนวนและความแข็งแกร่งของการเชื่อมต่อ ตรวจสอบให้แน่ใจว่าค่าน้ำหนักของเส้นเชื่อมไม่เป็นลบเพื่อให้การรับประกันของ Perron-Frobenius เป็นจริง

ฉันควรรายงาน eigenvector centrality ในบทความอย่างไร?

รายงานคะแนน eigenvector centrality ที่ปรับค่ามาตรฐานแล้ว (สูงสุด = 1) ระบุซอฟต์แวร์และเวอร์ชันที่ใช้ (เช่น NetworkX, igraph) ระบุว่าเครือข่ายเป็นแบบมีทิศทางหรือไม่มีทิศทาง และยืนยันว่าใช้ส่วนประกอบที่เชื่อมต่อกันที่ใหญ่ที่สุดหากกราฟไม่เชื่อมต่อกัน การแสดงภาพที่ระบายสีหรือปรับขนาดโหนดตามคะแนนจะช่วยในการตีความได้อย่างมาก

ความสัมพันธ์ระหว่าง eigenvector centrality กับ PageRank คืออะไร?

PageRank เป็นการขยาย eigenvector centrality แบบมีทิศทางและมีการหน่วง โดยเพิ่มปัจจัยการหน่วง (โดยทั่วไปคือ 0.85) และความน่าจะเป็นในการเคลื่อนย้ายแบบสม่ำเสมอเพื่อจัดการกับกราฟที่ไม่เชื่อมต่อกันและมีทิศทาง สำหรับเครือข่ายที่เชื่อมต่อกันแบบไม่มีทิศทาง PageRank และ eigenvector centrality จะให้การจัดอันดับที่เกือบจะเหมือนกัน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Bonacich, P. (1972). Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1), 113–120.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Eigenvector centrality. Wikipedia.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว