MẠNG XÃ HỘI VÀ CÁC VẤN ĐỀ PHÂN TÍCH MẠNG XÃ HỘI
GIỚI THIỆU VỀ MẠNG LƯỚI XÃ HỘI
Lý thuyết đồ thị là một lĩnh vực quan trọng trong Khoa học máy tính, nghiên cứu về các đồ thị bao gồm đỉnh (nút) và cạnh Các cạnh có thể có hướng hoặc vô hướng, tùy thuộc vào từng bài toán cụ thể Lý thuyết đồ thị được ứng dụng linh hoạt trong nhiều vấn đề như tìm đường đi ngắn nhất và sắp xếp lịch thi cho sinh viên Một trong những ứng dụng nổi bật của lý thuyết đồ thị là mô hình hóa mạng lưới xã hội.
Mạng lưới xã hội là cấu trúc xã hội kết nối cá nhân và tổ chức thông qua các mối quan hệ như tình bạn, tình yêu, và đồng nghiệp Mỗi cá nhân hoặc tổ chức được coi là một đỉnh trong đồ thị, trong khi các cạnh nối giữa các đỉnh thể hiện mối quan hệ xã hội giữa chúng Những mối quan hệ này tạo thành các nút thắt quan trọng trong mạng lưới, phản ánh sự liên kết và tương tác giữa các thành viên trong xã hội.
Một trong những mô hình trực quan phổ biến nhất trong thực tế là dịch vụ mạng xã hội trực tuyến, với Facebook, Twitter, Instagram và YouTube là những ví dụ điển hình Trong đó, Facebook minh họa cho mô hình mạng xã hội sử dụng đồ thị vô hướng, trong khi Twitter áp dụng đồ thị có hướng.
PHÂN TÍCH MẠNG LƯỚI XÃ HỘI
Phân tích mạng lưới xã hội (PTMLXH) là quá trình nghiên cứu cấu trúc xã hội thông qua lý thuyết đồ thị, trong đó các đỉnh (hay còn gọi là actor) và các cạnh (mối quan hệ) thể hiện các kết nối giữa các actor như cá nhân, tổ chức, doanh nghiệp, và băng đảng Các mối quan hệ này có thể bao gồm tương trợ, trao đổi thông tin và dịch vụ PTMLXH bao gồm các phương pháp chọn mẫu, thu thập và xử lý dữ liệu nhằm mô tả và phân tích các mối quan hệ giữa các actor, quy luật hình thành và biến chuyển của chúng, cũng như ảnh hưởng của các mối quan hệ xã hội đến hành vi của actor Tóm lại, PTMLXH nghiên cứu hành vi của actor ở mức độ vi mô, cấu trúc quan hệ mạng lưới ở mức độ vĩ mô, và sự tương tác giữa hai khía cạnh này.
CÁC ỨNG DỤNG CỦA PHÂN TÍCH MẠNG LƯỚI XÃ HỘI
Với sự phát triển công nghệ nhanh chóng, các thuật toán đồ thị ngày càng được chú trọng, trong đó phương pháp PTMLXH đã trở thành một công cụ đa ngành, không chỉ giới hạn trong xã hội học Ban đầu, PTMLXH chỉ là ứng dụng mô hình hóa xã hội, nhưng hiện nay nó được áp dụng rộng rãi trong nhiều lĩnh vực khoa học, đặc biệt là trong ngành khoa học máy tính, bao gồm các ứng dụng như truy hồi thông tin, khai phá dữ liệu và khoa học dữ liệu.
Sự đa dạng trong ứng dụng của PTMLXH khiến nó trở thành một kỹ thuật quan trọng, với khả năng áp dụng trong nhiều lĩnh vực như phân tích tội phạm, sinh học, kinh tế, lịch sử, địa lý và chính trị.
Các ứng dụng có thể kể đến như:
- “Detecting Key Players in Terrorist Networks” bởi Ala Berzinji, Lisa Kaati, Ahmed Rezine [5]
- Đề xuất kết bạn trên mạng xã hội trực tuyến
Các doanh nghiệp tiến hành khảo sát để hiểu nhu cầu của người tiêu dùng, từ đó phân tích dữ liệu nhằm phát triển sản phẩm mới phù hợp, không chỉ đáp ứng nhu cầu thị trường mà còn thúc đẩy doanh thu.
CÁC PHÉP ĐO TRONG MẠNG LƯỚI XÃ HỘI
CÁC HỆ SỐ ĐO LƯỜNG CƠ BẢN
2.1.1 HỆ SỐ CỐ KẾT ( DENSITY)
Hệ số cố kết của mạng lưới (Density) trong đồ thị phản ánh mức độ gắn kết và chặt chẽ của các mối quan hệ giữa các actor Khi hệ số cố kết cao, các mối quan hệ giữa các actor cũng trở nên mạnh mẽ hơn, dẫn đến sự tương trợ và hỗ trợ hiệu quả hơn Điều này cũng làm tăng cường sự điều tiết hành vi của các actor trong mạng lưới Đối với đồ thị vô hướng, công thức tính Density được áp dụng như sau:
𝑛(𝑛 − 1)/2 Đối với những đồ thị có hướng, ta sẽ có công thức tính Density như sau:
+ m: là tổng các mối liên hệ thực tế của mạng lưới
+ n: là tổng số đỉnh(nút) của mạng lưới
Giá trị của độ dày (density) dao động từ 0 đến 1; khi giá trị này càng gần 1, tính kết nối của mạng lưới càng mạnh mẽ Điều này dẫn đến sự tương trợ giữa các thành viên trong mạng lưới diễn ra hiệu quả hơn.
Ví dụ: Mạng lưới vô hướng gồm có 9 actor:
Mạng vô hướng được mô tả bởi 9 actor và 16 cạnh, thể hiện 16 mối liên hệ thực tế trong mạng lưới Từ đó, mật độ mạng được tính toán theo công thức 𝐷𝑒𝑛𝑠𝑖𝑡𝑦 = 9∗(9−1)/2 16, cho kết quả khoảng 0.44444.
Ví dụ: Mạng lưới có hướng gồm 7 actor:
Mạng có hướng bao gồm 7 actor và 11 cạnh, thể hiện 11 mối liên hệ thực tế trong mạng lưới Từ đó, ta có thể tính toán độ dày của mạng bằng công thức: 𝐷𝑒𝑛𝑠𝑖𝑡𝑦 = 7∗(7−1) / 11 ≈ 0.2619.
Theo J Scott cho rằng hệ số cố kết của mạng lưới phụ thuộc vào số lượng actor tham gia; cụ thể, khi số lượng actor tăng lên, hệ số cố kết sẽ giảm và ngược lại.
2.1.2 HỆ SỐ TRUNG TÂM TRỰC TIẾP ( DEGREE CENTRALITY)
Hệ số trung tâm trực tiếp (Degree Centrality) đo lường số lượng mối quan hệ trực tiếp của một actor với các thành viên khác trong mạng lưới, với giá trị từ 0 đến 1 Khi giá trị gần 1, tính trung tâm của actor càng lớn, cho thấy actor đó có nhiều kết nối hơn Actor này có thể là cá nhân nổi bật, nắm giữ nhiều thông tin và có ưu thế trong khai thác nguồn nhân lực, đồng thời ít phụ thuộc vào các actor khác Công thức tính toán giá trị của hệ số trung tâm trực tiếp trong PTMLXH sẽ được trình bày cụ thể.
+ k : Tổng số mối quan hệ trực tiếp của 𝑎𝑐𝑡𝑜𝑟𝑖
+ n : Tổng số actor trong mạng lưới
Trong một mạng lưới có hướng, chúng ta cần chú ý đến hai hệ số quan trọng: in-degree và out-degree Hệ số in-degree của một actor (diễn viên) là tổng số mối quan hệ trực tiếp mà actor đó nhận được, tương ứng với tổng số cạnh hướng đến actor Ngược lại, out-degree là tổng số mối quan hệ trực tiếp mà actor đó phát ra, tức là tổng số cạnh hướng từ actor đến các thành viên khác trong mạng lưới.
Ví dụ: Mạng vô hướng ví dụ hệ số trung tâm trực tiếp
Hình 3 Mạng vô hướng ví dụ hệ số trung tâm trực tiếp
Bảng Kết quả hệ số trung tâm trực tiếp dựa trên Hình 31
Ví dụ: Mạng có hướng ví dụ hệ số trung tâm trực tiếp
Hình 4 Mạng có hướng ví dụ hệ số trung tâm trực tiếp
Bảng Kết quả hệ2 số trung tâm trực tiếp dựa trên Hình 4
2.1 3 HỆ SỐ TRUNG TÂM LÂN CẬN (CLOSENESS CENTRALITY)
Hệ số trung tâm lân cận (Closeness Centrality) đo lường mức độ 'thân cận' của một actor trong mạng lưới, giúp xác định các thành viên gần gũi nhất với actor đó Sự 'gần gũi' này là yếu tố quan trọng thể hiện vị thế của actor, vì càng gần gũi với các thành viên khác, actor sẽ càng dễ dàng tiếp cận thông tin và có sức ảnh hưởng lớn hơn trong toàn bộ mạng lưới Việc tính toán hệ số này cũng rất đơn giản và có thể thực hiện dễ dàng.
+ n: Tổng số actor trong mạng lưới
+ ∑ 𝑑(𝑥, 𝑦): Tổng số ‘bước’ (step) của đoạn đường ngắn nhất mà 𝑎𝑐𝑡𝑜𝑟𝑖 phải đi để đến với mọi actor trong mạng
Ví dụ: Mạng vô hướng ví dụ hệ số trung tâm lân cận
Hình 5 Mạng vô hướng ví dụ hệ số trung tâm lân cận
Bảng Kết quả hệ số trung tâm lân cận dựa trên Hình 53
Tương tự như hệ số trung tâm trực tiếp, đối với đồ thị có hướng, hệ số trung tâm lân cận cũng có in-degree và out-degree
2.1 4 HỆ SỐ TRUNG TÂM TRUNG GIAN (BETWEENNESS
Hệ số trung tâm trung gian (Betweenness Centrality) là chỉ số quan trọng trong việc xác định một actor trung gian trong mạng lưới, người có vai trò quan trọng trong việc trao đổi thông tin Chỉ số này dao động từ 0 đến 1; khi giá trị gần 1, actor đó có nhiều mối quan hệ cần thông qua mình, từ đó tạo ra ảnh hưởng lớn đến dòng chảy thông tin trong hệ thống Actor này có khả năng kiểm soát và định hướng thông tin theo lợi ích cá nhân, đồng thời cũng là cầu nối thúc đẩy sự phối hợp giữa các thành viên khác trong mạng lưới.
+ 𝜎𝑥𝑦(𝑖): Tổng đường đi ngắn nhất giữa 2 𝑎𝑐𝑡𝑜𝑟 𝑥 và 𝑎𝑐𝑡𝑜𝑟𝑦 mà phải thông qua 𝑎𝑐𝑡𝑜𝑟𝑖
+ 𝜎𝑥𝑦: Tổng đường đi ngắn nhất giữa 2 𝑎𝑐𝑡𝑜𝑟𝑥 và 𝑎𝑐𝑡𝑜𝑟𝑦 trong toàn mạng lưới + n : Tổng số actor có trong mạng lưới
Ví dụ: Mạng vô hướng ví dụ hệ số trung tâm trung gian
Hình 6 Mạng vô hướng ví dụ hệ số trung tâm trung gian Đỉnh L M N O P Q R
Bảng Kết quả hệ số trung tâm trung gian dựa trên Hình 64
Tương tự như 2 hệ số ở trên, đối với đồ thị có hướng, hệ số trung tâm trung gian cũng có in-degree và out-degree
2.1 5 HỆ SỐ PHÂN CỤM (CLUSTERING COEFFICIENT)
Hệ số phân cụm, được phát hiện bởi Watts và Strogatz, là tiêu chuẩn đánh giá mức độ gắn kết giữa các actor trong mạng lưới Hệ số này được xác định dựa trên các actor láng giềng có mối liên kết với nhau, tạo thành những mạng con Nếu một actor chỉ có một láng giềng, thì không thể hình thành mạng con giữa actor đó và láng giềng.
• Hệ số phân cụm cục bộ (Local Clustering Coefficient)
Hệ số phân cụm cục bộ đo lường mức độ gắn kết giữa các actor láng giềng của một actor cụ thể Công thức tính toán hệ số này được áp dụng cho mạng lưới vô hướng.
𝑘 𝑖 (𝑘 − 1) 𝑖 :𝑣𝑗, 𝑣𝑘∈ 𝑁𝑖; 𝑒𝑗𝑘∈ 𝐸 Đối với mạng lưới có hướng ta có công thức:
+ 𝑁𝑖 : tập hợp các actor láng giềng của 𝑎𝑐𝑡𝑜𝑟𝑖
+ E : tập hợp tất cả các mối quan hệ (cạnh) của mạng lưới.
+ 𝑒𝑗𝑘: cạnh kết nối của 𝑎𝑐𝑡𝑜𝑟𝑗 và 𝑎𝑐𝑡𝑜𝑟𝑘
+ 𝑘𝑖: số lượng láng giềng của 𝑎𝑐𝑡𝑜𝑟𝑖
+ |𝑒𝑗𝑘|: Tổng số cạnh kết nối giữa các actor trong tập 𝑁𝑖
Sau khi xác định hệ số phân cụm cục bộ cho từng actor trong mạng lưới, chúng ta có thể tính toán hệ số phân cụm cục bộ trung bình Điều này giúp đánh giá mức độ gắn kết tổng thể của toàn bộ mạng lưới Công thức tính toán sẽ được áp dụng để thu được kết quả chính xác.
+ n: Số actor của toàn mạng lưới
• Hệ số phân cụm toàn cục (Global Clustering Coefficient)
Hệ số phân cụm toàn cục phản ánh mức độ gắn kết của toàn bộ mạng lưới, khác với hệ số phân cụm cục bộ trung bình, dựa trên bộ ba đỉnh ngẫu nhiên trong mạng Để bộ ba này được coi là một clique, nó cần tạo thành một chu trình tam giác.
+ 𝑛𝑢𝑚𝑏𝑒𝑟 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠𝑜𝑓 : tổng số tam giác được tạo bởi tất cả các bộ ba trong mạng lưới
+ 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎𝑙𝑙 𝑡𝑟𝑖𝑝𝑙𝑒𝑡𝑠: tổng số các actor tạo thành bộ ba
Hình 7 Ví dụ về phân cụm
Bảng kết quả phân cụm bao gồm hệ số phân cụm cục bộ, hệ số phân cụm trung bình và hệ số phân cụm toàn cục, như được trình bày trong Hình 7.
2.2 NHÂN T CHÍNH (KEY PLAYERS) VÀ CÁCH NHỐ ẬN BIẾT
2.2.1 KHÁI NI M NHÂN T CHÍNH (KEY PLAYERS) Ệ Ố
Nhân tố chính trong mạng lưới được xác định là những yếu tố quan trọng nhất, giữ vai trò quyết định trong sự vận hành của mạng Các actor này có thể là thủ lĩnh, người đưa ra quyết định, hoặc có sức ảnh hưởng lớn, dẫn dắt ý kiến và kết nối các thành viên khác Họ cũng có khả năng kiểm soát luồng thông tin, đóng vai trò cầu nối giữa các nguồn thông tin trong mạng lưới Với những lợi thế này, các nhân tố chính có thể chi phối toàn bộ cấu trúc và hoạt động của mạng lưới.
2.2.2 CÁCH NH Ậ N BI Ế T KEY PLAYERS
SIGNED GRAPH: CÁC VẤN ĐỀ VÀ ỨNG DỤNG
Học thuyết địa vị có thể được áp dụng để phân tích mạng lưới điều tra tội phạm, trong đó A có địa vị cao nhất, theo sau là D, C và B Cụ thể, A đứng đầu băng đảng, D có địa vị cao hơn C, C cao hơn B, và B có địa vị thấp nhất Qua đó, chúng ta có thể khẳng định rằng A chính là thủ lĩnh của băng đảng.
NHẬN BIẾT CỘNG ĐỒNG (COMMUNITY DETECTION)
MODULARITY
Phương pháp Modularity là một thuật toán phổ biến trong việc phát hiện cộng đồng trong mạng lưới, được xem như một trong những phương pháp nguyên thủy nhất cho vấn đề phân cụm Thuật toán này đo cường độ phân chia của mạng thành các cộng đồng, với đồ thị có modularity cao thể hiện các kết nối dày đặc giữa các nút trong cùng một mô đun và thưa thớt giữa các mô đun khác nhau Quá trình của thuật toán gồm hai giai đoạn: đầu tiên, tối ưu hóa mô đun cục bộ để tìm các cộng đồng nhỏ; sau đó, các đỉnh trong cùng một cộng đồng được tập hợp lại để xây dựng một mạng lưới mới Độ phức tạp của thuật toán được ước tính là 𝑂(𝑛log𝑛), mặc dù chưa được chứng minh chính thức.
Giả sử mạng lưới có tất cả n đỉnh Cụ thể, ta chi mạng lưới thành 2 nhóm và đặt
𝑠𝑖= 1 nếu đỉnh i thuộc nhóm 1 và 𝑠𝑖= −1 nếu đỉnh i thuộc nhóm 2 Ta có công thức tính Modularity như sau:
+ 𝐴𝑖𝑗: giá trị của ma trận kề A tại hàng i và cột j
+ m: Tổng số actor của mạng lưới
Từ công thức, ta có giá trị 𝑄 nằm trong khoảng [−1; 1] Mô đun càng cao thì kết quả đạt được càng tốt, nhưng điều này cũng khiến phương pháp Modularity bị hạn chế, khó nhận diện các cộng đồng nhỏ.
GRIVAN NEWMAN’S ALGORITHM
Thuật toán Girvan – Newman là một trong những thuật toán nổi bật nhất trong phương pháp phân chia mạng, có ý nghĩa lịch sử quan trọng trong việc phát hiện cộng đồng Ý tưởng chính của thuật toán này là xác định và loại bỏ các cạnh kết nối giữa các cộng đồng trong mạng, những cạnh này được coi là ‘trung gian’ Bất kỳ đường đi nào giữa hai đỉnh thuộc hai cộng đồng khác nhau đều phải đi qua ít nhất một trong những cạnh này Do đó, bằng cách thiết lập các đường đi giữa tất cả các đỉnh trong mạng và xác định các cạnh được sử dụng nhiều nhất, chúng ta có thể loại bỏ chúng để phân chia mạng thành các cộng đồng riêng biệt.
Nội dung của thuật toán Girvan – Newman như sau:
1 Tính hệ số trung tâm trung gian của tất cả các cạnh trong mạng
2 Loại bỏ những cạnh có hệ số cao nhất (Nếu có từ 2 trở lên có hệ số giống nhau ta có thể loại bỏ ngẫu nhiên 1 cạnh hoặc loại bỏ tất cả các cạnh)
3 Tính toán lại hệ số trung tâm trung gian cho tất cả các cạnh bị ảnh hưởng bởi bước 2
4 Lặp lại bước 2 cho đến khi không còn cạnh nào trong mạng lưới Thuật toán Girvan – Newman đưa lại kết quả tương đối tốt trong nhiều trường hợp nhưng có hai nhược điểm chính Thứ nhất, thuật toán Girvan – Newman không xác định trước được số cộng đồng mà mạng phân chia ra sẽ là bao nhiêu, và với rất nhiều phép phân vùng như vậy, khó có thể xác định được phép phân vùng nào mang lại hiệu quả tốt nhất Thứ hai, thuật toán có độ phức tạp cao, ới n đỉv nh và m cạnh ta sẽ có độ phức tạp là 𝑂(𝑚𝑛) trong mỗi bước lặp, và tổng th i gian tính toán là ờ 𝑂(𝑚 𝑛) 2 mỗi khi cho mỗi bước xóa c nh và vạ ới trường h p x u nh t ta s ợ ấ ấ ẽ có độ phức tạp là 𝑂(𝑛 3 ) Với các nhược điểm như trên, các nhà khoa học đã tìm cách cải tiến để cho phương pháp tốt hơn, điều đó đã dẫn tới họ của phương pháp Girvan – Newman nhưng sẽ không được đề cập trong báo cáo này
NODE SIMILARITY BASED ALGORITHM (NSBA)
NSBA so sánh các đỉnh dựa trên láng giềng của chúng, xác định rằng hai đỉnh tương tự nếu chúng có cùng láng giềng Để thực hiện điều này, hệ số Jaccard được áp dụng để đo lường mức độ tương đồng giữa hai đỉnh Công thức tính hệ số Jaccard cho hai đỉnh A và B là
Thuật toán so sánh hai đỉnh A và B thông qua công thức |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| Nó đánh giá mối quan hệ giữa hai đỉnh này và trả về một giá trị từ 0 đến 1 Giá trị gần 1 cho thấy hai đỉnh ngày càng giống nhau, trong khi giá trị gần 0 chỉ ra sự khác biệt giữa chúng.
LABEL PROPAGATION COMMUNITY DETECTION (LPA)
Nghiên cứu cấu trúc cộng đồng trong mạng xã hội lớn yêu cầu một thuật toán nhanh và chính xác để nhận diện cộng đồng Khi kích thước cộng đồng tăng, độ phức tạp của thuật toán cần duy trì gần với tuyến tính Thuật toán lan truyền nhãn (LPA) nổi bật nhờ vào độ phức tạp thấp và dễ thực hiện, khiến nó trở thành một trong những phương pháp hiệu quả nhất trong nhận diện cộng đồng Ý tưởng của thuật toán này được nghiên cứu bởi Bagrow, bắt đầu với một đỉnh được gán nhãn, sau đó thuật toán sẽ lan truyền đến từng đỉnh trong mạng lưới cho đến khi không còn khả năng lan truyền.
Trong đồ thị, một đỉnh được gọi là nội đỉnh nếu tất cả các láng giềng của nó có cùng nhãn, trong khi đỉnh không phải nội đỉnh được gọi là ngoại đỉnh Các đỉnh đã từng thay đổi nhãn sẽ không thay đổi nhãn nữa và được gọi là đỉnh bị động, trong khi đỉnh không bị động được gọi là đỉnh chủ động Tất cả các nội đỉnh đều là bị động, trong khi ngoại đỉnh có thể là chủ động hoặc bị động tùy thuộc vào láng giềng của nó Mỗi đỉnh sẽ có một trong ba thuộc tính: nội bị động, ngoại bị động hoặc ngoại chủ động Thuật toán sẽ kết thúc khi tất cả các đỉnh đều trở thành bị động, và các đỉnh chủ động sẽ được lưu giữ trong danh sách đỉnh chủ động.
Thuật toán có nội dung như sau:
1 Vào thời điểm t = 0, đưa tất cả các đỉnh vào active node list
2 Ngẫu nhiên chọn một đỉnh chủ động từ active node list, gọi đỉnh này là i, và thay đổi nhãn của đỉnh này theo định nghĩa đã được nêu ở trên Bởi vì chỉ có những đỉnh chủ động mới được đặt ở vị trí đầu trong danh sách và những đỉnh này sẽ ở lại trong danh sách miễn là vẫn còn thuộc tính chủ động, những đỉnh được chọn sẽ thay đổi nhãn của mình trong quá trình cập nhật
3 Đầu tiên, kiểm tra xem những đỉnh đã được cập nhật đã mang thuộc tính bị động hay chưa, nếu rồi thì xóa đỉnh đó khỏi danh sách Tiếp theo, kiểm tra xem sự thay đổi tất cả láng giềng của đỉnh đó thông qua ba bước (1) nếu một nội đỉnh trở thành đỉnh ngoại chủ động, thêm đỉnh đó vào active node list (2) Loại bỏ những đỉnh láng giềng chủ động mà đã trở thành bị động ra khỏi active node list (3) Thêm những đỉnh láng giềng ngoại bị động mà đã trở thành chủ động vào active node list
4 N u active node list r ng thì d ng thu t toán; n u không ế ỗ ừ ậ ế 𝑡 += 1 và quay lại bước 2.
DEMO
DEMO HỆ SỐ CỐ KẾT TRÊN PYTHON
4.1.1 GIẢI THUẬT Đầu tiên ta cần biểu diễn đồ thị trên ma trận kề, tiếp theo ta cần tìm số cạnh của đồ thị dựa trên ma trận kề vừa biểu diễn Giải thuật tìm cạnh của đồ thị trên ma trận kề như sau:
1 Tạo một biến number_of_Edges và gán biến đó bằng 0, đồng thời cho một biến i = 0
2 Duyệt từng phần từ trong hàng thứ i của ma trận kề, nếu phần tử này khác 0 thì number_of_Edges cộng thêm 1 đơn vị.
3 Nếu i bé hơn kích cỡ ma trận thì i cộng thêm một và quay lại bước
2, nếu không dừng thuật toán
4 Kết quả trả về số cạnh của đồ thị
Lưu ý: Đối với đồ thị vô hướng thì 𝑛𝑢𝑚𝑏𝑒𝑟 𝐸𝑑𝑔𝑒𝑠 =𝑜𝑓 𝑛𝑢𝑚𝑏𝑒𝑟 𝐸𝑑𝑔𝑒𝑠 𝑜𝑓
2 khi vừa kết thúc vòng lặp
Khi xác định số cạnh của đồ thị, chúng ta có thể sử dụng công thức để tính hệ số cố kết Đối với đồ thị vô hướng, công thức tính mật độ (Density) sẽ được áp dụng như sau:
𝑛(𝑛 − 1)/2 Đối với những đồ thị có hướng, ta sẽ có công thức tính Density như sau:
+ m: là tổng các mối liên hệ thực tế (các cạnh) của mạng lưới
+ n: là tổng số đỉnh(nút) của mạng lưới
Hình 10 Ví dụ demo hệ số cố kết Đối với ví dụ demo hệ số cố kết, ta sẽ có ma trận kề biểu diễn đồ thị như sau:
Ta sẽ tìm số cạnh của đồ thị bằng giải thuật đã được nêu 4.1.1 Áp dụng công th c ta có ứ 𝐷 ≈ 0.44444, với số cạnh = 16, số đỉnh = 9.
Kết quả cuối cùng của demo code Python:
Hình 11 Demo hệ số cố kết trên Python
DEMO HỆ SỐ TRUNG TÂM TRỰC TIẾP TRÊN PYTHON
4.2.1 GIẢI THUẬT Đầu tiên ta cần biểu diễn đồ thị trên ma trận kề, tiếp theo ta cần phải tìm được danh sách các bậc của đỉnh theo thứ tự Giải thuật tìm bậc của từng cạnh trong đồ thị vô hướng như sau:
1 Tạo một list rỗng, gọi list này là Degree = [], đồng thời cho một biến i = 0
2 Tạo một biến Edges và gán biến này bằng 0
3 Duyệt từng phần từ trong hàng thứ i của ma trận kề, nếu phần tử này khác 0 thì Edges cộng thêm 1 đơn vị
4 Khi đã duyệt hết tất cả các phần tử trong hàng thứ i của ma trận kề, Degree.append(Edges) Nếu i bé hơn kích cỡ ma trận thì i cộng thêm một và quay lại bước 2, nếu không dừng thuật toán
5 Kết quả trả về list Degree là số bậc của từng đỉnh theo thứ tự Với mỗi phần tử trong list Degree, ta sử dụng công thức sau đây để tính hệ số trung tâm trực tiếp cho từng đỉnh:
+ k : Tổng số mối quan hệ trực tiếp của 𝑎𝑐𝑡𝑜𝑟𝑖 (Tổng số bậc của 𝑎𝑐𝑡𝑜𝑟𝑖)
+ n : Tổng số actor trong mạng lưới Đối với đồ thị có hướng ta có giải thuật:
• Đối với bậc out – degree ta áp dụng tương tự như giải thuật của đồ thị vô hướng trên ma trận kề
• Đối với bậc in – degree ta áp dụng tương tự như giải thuật của đồ thị vô hướng trên chuyển vị của ma trận kề
• Áp dụng công thức tính hệ số trung tâm trực tiếp ta sẽ có bậc của out – degree và in – degree với các list InDegree và OutDegree.
Hình 12 Ví dụ demo 1 hệ số trung tâm trực tiếp Đối với demo 1 hệ số trung tâm trực tiếp, ta sẽ có ma trận kề như sau:
Ta tìm danh sách bậc của đồ thị như giải thuật đã nêu ở 4.2.1
Sau đó áp dụng công thức ta kết quả:
Hình 13 Ví dụ demo 2 hệ số trung tâm trực tiếp Đối với demo 2 hệ số trung tâm trực tiếp, ta sẽ có ma trận kề như sau:
Ta tìm danh sách in degree và out degree – – của đồ thị như giải thuật đã nêu ở 4.2.1
Sau đó áp dụng công thức ta kết quả:
Hình 14 Demo hệ số trung tâm trực tiếp trên Python
DEMO HỆ SỐ TRUNG TÂM LÂN CẬN TRÊN PYTHON
Chúng tôi sử dụng thư viện networkx để giải quyết bài toán Đầu tiên, chúng tôi áp dụng các lệnh add_node (add_nodes_from) và add_edge (add_edges_from) để xây dựng đồ thị theo yêu cầu.
Ta có giải thuật như sau:
1 Tạo một set rỗng, gọi set này là là Dict_Cc dùng để chứa các hệ số trung tâm lân cận của từng đỉnh theo thứ tự, đồng thời cho một biến i = 0
2 Duyệt phần tử thứ i của đồ thị (theo thứ tự đã cho trước đó), đồng thời đặt một biến d = 0
3 Duyệt tất cả các kết nối của đỉnh i tới các đỉnh khác trong đồ thị và tìm đường đi ngắn nhất của đỉnh i đến từng đỉnh, với mỗi đường đi ngắn nhất từ đỉnh i tới các đỉnh lần lượt ta sẽ có biến step đại diện cho bước ngắn nhất từ đỉnh i đến đỉnh đó, cứ mỗi lần như vậy d được cập nhật 𝑑 += 𝑠𝑡𝑒𝑝 Đồng thời áp dụng công thức tính hệ số trung tâm lân cận có công thức như sau:
+ n: Tổng số actor trong mạng lưới
+ ∑ 𝑑(𝑥, 𝑦): Tổng số ‘bước’ (step) của đoạn đường ngắn nhất mà 𝑎𝑐𝑡𝑜𝑟𝑖phải đi để đến với mọi actor trong mạng.
Sau đó Dict_Cc.add(𝐶 𝑐 )
4 Nếu i bé hơn số đỉnh của đồ thị thì i tăng một đơn vị và quay lại bước 2 Nếu không kết thúc thuật toán
5 Kết quả trả về là set Dict_Cc chứa hệ số trung tâm lân cận của tất cả các đỉnh trong đồ thị
Hình 15 Ví dụ demo hệ số trung tâm lân cận
Sử dụng các lệnh để tạo đồ thị: import networkx as nx g = nx.Graph() g.add_nodes_from([1,2,3,4,5,6]) g.add_edges_from([(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)]) Áp dụng giải thuật đã trình bày ở 4.3.1
Hình 16 Demo hệ số trung tâm lân cận trên Python
DEMO HỆ SỐ TRUNG TÂM TRUNG GIAN TRÊN PYTHON
Chúng tôi sử dụng thư viện networkx để giải quyết bài toán, bắt đầu bằng việc sử dụng các lệnh add_node (add_nodes_from) và add_edge (add_edges_from) để tạo ra đồ thị theo yêu cầu.
Ta có giải thuật như sau:
1 Tạo một set rỗng, gọi set này là là Dict_Cb dùng để chứa các hệ số trung tâm lân cận của từng đỉnh theo thứ tự, đồng thời cho một biến i = 0
2 Duyệt phần tử thứ i của đồ thị (theo thứ tự đã cho trước đó), đồng thời đặt một biến b = 0
3 Duyệt tất cả các kết nối của đỉnh x tới tất cả các đỉnh khác trong đồ thị (trừ đỉnh i) và tìm đường đi ngắn nhất của đỉnh đến từng x đỉnh, với mỗi đường đi ngắn nhất từ đỉnh tới các đỉnh lần lượt ta x sẽ có biến count đại diện cho số lần xuất hiện của đỉnh i trong đường đi đó Sau khi đã duyệt xong ta áp dụng công thức tính hệ số trung tâm trung gian:
+ n : Tổng số actor có trong mạng lưới Sau đó Dict_Cb.add(𝑪𝑩)
4 Nếu i bé hơn số đỉnh của đồ thị thì i tăng một đơn vị và quay lại bước 2 Nếu không kết thúc thuật toán
5 Kết quả trả về là set Dict_Cb chứa hệ số trung tâm trung gian của tất cả các đỉnh trong đồ thị
Hình 17 Ví dụ demo hệ số trung tâm trung gian
Sử dụng các lệnh để tạo đồ thị: import networkx as nx a = nx.Graph() a.add_nodes_from(['L','M','N','O','P','Q','R']) a.add_edges_from([('L','M'),('L','N'),('L','O'),
('P','Q')]) Áp dụng giải thuật đã trình bày ở 4.4.1
Hình 18 Demo hệ số trung tâm trung gian trên Python
DEMO HỆ SỐ PHÂN CỤM TRÊN PYTHON
Chúng tôi sử dụng thư viện networkx để giải quyết bài toán Đầu tiên, chúng tôi áp dụng các lệnh add_node (add_nodes_from) và add_edge (add_edges_from) để xây dựng đồ thị theo yêu cầu.
Ta có giải thuật như sau:
1 Tạo một set rỗng, gọi set này là là Dict_Cluster dùng để chứa các hệ số phân cụm cục bộ của từng đỉnh theo thứ tự, đồng thời cho một biến i = 0
2 Duyệt phần tử thứ i của đồ thị (theo thứ tự đã cho trước đó), đồng thời đặt một biến b = 0
3 Với đỉnh thứ i của đồ thị, ta xét xem đỉnh đó có bao nhiêu láng giềng và các láng giềng đó là đỉnh nào Sau đó ta tìm bậc của đỉnh
I, tiếp theo đó tìm tổng số cạnh kết nối của các láng giềng của đỉnh i, với điều kiện cạnh đó không nối đến đỉnh i Gọi tổng số cạnh được vừa tìm được là e Sau khi đã duyệt xong ta áp dụng công thức tính hệ số phân cụm cục bộ: Đối với mạng lưới vô hướng ta có công thức:
𝑘𝑖(𝑘 − 1)𝑖 Đối với mạng lưới có hướng ta có công thức:
+ 𝑘 𝑖 : số bậc của đỉnh i Sau đó Dict_Clustering.add(𝐶𝑖)
4 Nếu i bé hơn số đỉnh của đồ thị thì i tăng một đơn vị và quay lại bước 2 Nếu không kết thúc thuật toán
5 Kết quả trả về là set Dict_Clustering chứa hệ số phân cụm cục bộ của tất cả các đỉnh trong đồ thị
Khi đã có tất cả hệ số phân cụm cục bộ ta có thể tính được hệ số phân cụm cục bộ trung bình với công thức:
Hệ số phân cụm toàn cục được xác định bằng cách duyệt qua đồ thị để tìm các chu trình tam giác hình thành từ ba đỉnh Đối với mỗi đỉnh, ta cần kiểm tra số lượng cạnh kết nối để tính tổng số đỉnh có khả năng tạo thành bộ ba Công thức tính hệ số phân cụm toàn cục sẽ giúp chúng ta hiểu rõ hơn về cấu trúc của đồ thị.
+ 𝑛𝑢𝑚𝑏𝑒𝑟 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠𝑜𝑓 : tổng số tam giác được tạo bởi tất cả các bộ ba trong mạng lưới
+ 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎𝑙𝑙 𝑡𝑟𝑖𝑝𝑙𝑒𝑡𝑠: tổng số các actor tạo thành bộ ba
Hình 19 Ví dụ demo hệ số phân cụm
Sử dụng các lệnh để tạo đồ thị: import networkx as nx b = nx.Graph() b.add_nodes_from(['A','B','C','D','E','F','G']) b.add_edges_from([('A','B'),('A','C'),
('E','F'),('E','G')]) Áp dụng giải thuật đã trình bày ở 4.5.1
Hệ số phân cụm toàn cục: 0.5294117647058824
Hệ số phân cụm cục bộ trung bình: 0.5714285714285714
Hình 20 Demo hệ số phân cụm cục bộ trên Python
