Phát hiện cộng đồng trong đồ thị xã hội


Đỗ Cao Thọ
6 năm trước
Hữu ích 9 Chia sẻ Viết bình luận 0
Đã xem 1794

Khi phân tích mạng xã hội, một vấn đề phổ biến là làm thế nào để phát hiện các cộng đồng, chẳng hạn như các nhóm người biết hoặc tương tác thường xuyên với nhau. Cộng đồng là một sơ đồ của đồ thị trong đó kết nối dày đặc khác thường.

Trong blog này, tôi sẽ liệt kê một số thuật toán phổ biến về tìm kiếm cộng đồng.

Trước hết, phát hiện cộng đồng có thể nghĩ về vấn đề phân vùng đồ thị. Trong trường hợp này, một nút sẽ thuộc về không quá một cộng đồng. Nói cách khác, cộng đồng không trùng lặp với nhau.

Loại bỏ cạnh giữa cao

Trực giác là các thành viên trong một cộng đồng được kết nối dày đặc và có nhiều con đường để tiếp cận với nhau. Mặt khác, các nút từ các cộng đồng khác nhau đòi hỏi các liên kết giữa các cộng đồng để tiếp cận với nhau và các liên kết giữa các cộng đồng này có xu hướng có điểm giữa các điểm cao.

Do đó, bằng cách loại bỏ các liên kết giữa độ cao này, biểu đồ sẽ được phân tách thành các cộng đồng.

Thuật toán:
  1. Đối với mỗi cạnh, hãy tính điểm giữa các cạnh
  2. Loại bỏ các cạnh có điểm giữa cao nhất
  3. Cho đến khi có đủ sự phân biệt
Tuy nhiên, trong khi phương pháp này đạt được kết quả tốt, nó rất chậm và không hoạt động hiệu quả khi có hơn vài nghìn nút với các cạnh dày đặc.

Phân cụm phân cấp

Đây là một cách tiếp cận rất chung của việc phát hiện các cộng đồng. Một số thước đo khoảng cách (hoặc điểm tương đồng) được xác định và tính toán giữa mỗi cặp nút trước tiên. Sau đó,  kỹ thuật cụm phân cấp cổ điển  có thể được áp dụng. Khoảng cách nên được chọn sao cho nhỏ giữa các thành viên trong một cộng đồng và lớn giữa các thành viên của cộng đồng khác nhau.

Đi bộ ngẫu nhiên

Đi bộ ngẫu nhiên có thể được sử dụng để tính khoảng cách giữa mỗi cặp nút-B và nút-C. Bây giờ hãy tập trung vào đồ thị vô hướng. Một người đi bộ ngẫu nhiên bắt đầu tại nút B, ném xúc xắc và có xác suất beta rằng nó chọn ngẫu nhiên một người hàng xóm để truy cập dựa trên trọng lượng của các liên kết và với xác suất 1 - beta rằng nó sẽ dịch chuyển trở lại nút-v ban đầu. Tại một số lượng vô hạn các bước, phân phối xác suất hạ cánh trên nút-w sẽ cao nếu nút-B và nút-C thuộc cùng một cộng đồng. Trực giác ở đây là walker ngẫu nhiên có xu hướng bị mắc kẹt trong cộng đồng nên tất cả các nút có phân phối xác suất cao có xu hướng nằm trong cùng một cộng đồng như nút-B (nơi bắt đầu walker ngẫu nhiên).

Lưu ý rằng việc chọn beta là quan trọng. Nếu nó quá lớn (gần 1), thì xác suất sau khi hội tụ không phụ thuộc vào nút bắt đầu (nghĩa là: phân phối xác suất chỉ phản ánh tính trung tâm của mỗi nút chứ không phải cộng đồng của nút bắt đầu). Nếu beta quá nhỏ (gần bằng 0), thì walker sẽ chết quá nhanh trước khi nó khám phá hoàn toàn kết nối của cộng đồng.

Có một giải pháp phân tích cho vấn đề này.


Cho phép M là ma trận chuyển tiếp trước mỗi cặp nút. V đại diện cho phân phối xác suất của nơi đi bộ ngẫu nhiên.


 "Khoảng cách" giữa nút-B và mọi nút khác là hàm riêng của M. Chúng ta có thể lặp lại tương tự để tìm ra khoảng cách của tất cả các cặp nút, sau đó đưa kết quả vào thuật toán phân cụm theo cấp bậc.

Tuyên truyền nhãn

Ý tưởng cơ bản là các nút quan sát hàng xóm của nó và đặt nhãn riêng của nó là phần lớn các hàng xóm của nó.
  1. Các nút ban đầu được gán với một nhãn duy nhất.
  2. Trong mỗi vòng, mỗi nút kiểm tra nhãn của tất cả các lân cận được đặt nhãn riêng của nó là phần lớn các hàng xóm của nó, khi có một cà vạt, người chiến thắng được chọn ngẫu nhiên.
  3. Cho đến khi không còn thay đổi bài tập nhãn

Tối ưu hóa mô đun

Trong một cộng đồng, xác suất 2 nút có liên kết phải cao hơn nếu liên kết chỉ được hình thành ngẫu nhiên trong toàn bộ biểu đồ.

xác suất của liên kết ngẫu nhiên = deg (nút-B) * deg (nút-C) / (N * (N-1))
Liên kết thực tế = Ma trận điều chỉnh [B, C]

Xác định com (B) là cộng đồng của nút- B, com (C) là cộng đồng của nút-C 

Vì vậy, một hàm tiện ích "Modularity" được tạo như sau ...
sum_over_v_w ((thực tế - ngẫu nhiên) * delta (com (B), com (C))) Bây giờ chúng ta kiểm tra các cộng đồng có thể chồng chéo. tức là: Một nút có thể thuộc về nhiều hơn một cộng đồng.




Tìm Clique

Phát hiện cộng đồng đơn giản thường bắt đầu với các cửa hàng. Clique là một sơ đồ con cho dù mọi nút được kết nối với bất kỳ nút nào khác. Trong K-Clique, có các nút K và liên kết K ^ 2 giữa chúng.

Tuy nhiên, cộng đồng có định nghĩa lỏng lẻo hơn, chúng tôi không yêu cầu mọi người biết mọi người khác trong cộng đồng, nhưng chúng tôi cần họ biết "đủ" (có thể là một tỷ lệ nhất định) của những người khác trong cộng đồng. K-core có định nghĩa thoải mái hơn, nó yêu cầu các nút của lõi K phải có kết nối với ít nhất K thành viên khác. Có một số thư giãn ít phổ biến hơn, K-Clan yêu cầu mọi nút để kết nối với mọi thành viên khác trong các bước K (độ dài đường dẫn nhỏ hơn K). K-plex yêu cầu nút kết nối với (N - K) thành viên trong nút trong đó N tổng số thành viên trong K-plex.

Cộng đồng được định nghĩa là K-core được tìm thấy, hoặc K-clan hoặc K-plex.

Phân chia K-Clique

Một cách phổ biến khác để tìm kiếm cộng đồng là bằng cách lăn qua K-Clique liền kề. Hai K-Clique liền kề nếu chúng chia sẻ các nút K-1. K là một tham số mà chúng ta cần chọn dựa trên mức độ chúng ta mong đợi cộng đồng nên có.

Thuật toán được minh họa trong sơ đồ sau.





K-Clique percolation là một cách phổ biến để xác định các cộng đồng có khả năng chồng chéo lẫn nhau.

Hữu ích 9 Chia sẻ Viết bình luận 0
Đã xem 1794