Một mạng xã hội là một tập thông tin hétérogène và đa quan hệ được mô tả bởi một đồ thị. Đồ thị thường rất lớn, với các nút tương ứng với các đối tượng và các cạnh tương ứng với các kết nối mô tả các mối quan hệ hoặc kết nối giữa các đối tượng. Cả nút và kết nối đều có thuộc tính. Các đối tượng có thể có nhãn lớp. Các liên kết có thể là một chiều và không cần phải là nhị phân.
Đặc điểm của Mạng Xã Hội
Có các đặc điểm sau của mạng xã hội:
Quy luật lũy thừa làm dày đặc (Densification power-law) – Trước đây cho rằng khi mạng phát triển, số bậc tăng tuyến tính theo số nút. Điều này được gọi là giả thuyết bậc trung bình không đổi. Tuy nhiên, các thí nghiệm rộng rãi đã cho thấy ngược lại, mạng trở nên dày đặc hơn theo thời gian với bậc trung bình tăng lên (vì vậy, số cạnh tăng siêu tuyến tính theo số nút). Việc làm dày đặc tuân theo quy luật lũy thừa làm dày đặc (hoặc quy luật lũy thừa tăng trưởng), định nghĩa:
$$e(t)\propto n(t)^{a}$$
trong đó e(t) và n(t) lần lượt định nghĩa số cạnh và nút của đồ thị tại thời điểm t, và số mũ a thường nằm chặt chẽ giữa 1 và 2. Nếu a = 1, điều này tương ứng với bậc trung bình cố định theo thời gian, trong khi a = 2 tương ứng với đồ thị hoàn toàn dày đặc nơi mỗi nút có cạnh đến một phần cố định của tất cả các nút.
Đường kính co lại (Shrinking diameter) – Đã được chứng minh thực nghiệm rằng đường kính hiệu quả có xu hướng giảm khi mạng tăng. Điều này mâu thuẫn với quan điểm trước đó rằng đường kính tăng chậm như một hàm của kích thước mạng.
Xét một web trích dẫn, nơi nút là các bài báo và trích dẫn từ bài này sang bài khác được biểu thị bằng cạnh có hướng. Out-links của nút v (định nghĩa các bài báo được trích dẫn bởi v) bị "đóng băng" tại thời điểm nó tham gia đồ thị. Khoảng cách giảm dần giữa các cặp nút do đó xảy ra do các bài báo sau này đóng vai trò "cầu nối" bằng cách trích dẫn các bài báo trước từ nhiều lĩnh vực khác nhau.
Phân phối out-degree và in-degree đuôi nặng (Heavy-tailed out-degree and in-degree distributions) – Các out-degree đa dạng cho một nút có xu hướng tuân theo phân phối đuôi nặng quan sát theo quy luật lũy thừa, 1/na, trong đó n là thứ hạng của nút theo thứ tự giảm dần out-degree và thường 0 < a < 2.
Giá trị a càng nhỏ thì đuôi càng nặng. Hiện tượng này được định nghĩa trong mô hình liên kết ưu tiên, nơi mỗi nút mới kết nối với mạng hiện có bằng một số out-links cố định, theo quy tắc giàu có càng giàu. In-degree cũng tuân theo phân phối đuôi nặng, mặc dù ảnh hưởng của nó bị lệch hơn so với phân phối out-degree.