Gần đây, đồ thị đã nhận được rất nhiều sự chú ý — từ ngành khoa học đời sống đến mạng xã hội. Việc sử dụng các biểu đồ tri thức để lưu trữ thông tin và để có được suy luận phong phú hơn đã trở nên rất phổ biến. Nghiên cứu về mạng lưới thần kinh đồ thị đang giải quyết nhiều vấn đề hiện có và thiết lập các tiêu chuẩn mới.

Trong phần này, chúng ta sẽ hiểu loại dữ liệu nào nên được biểu diễn tốt nhất với cấu trúc dữ liệu biểu đồ và tìm hiểu các biểu đồ khác nhau. Trong các phần tiếp theo của loạt bài viết này, chúng ta sẽ khám phá nhiều hơn về mạng nơ-ron đồ thị và thử một số thao tác thực hành.

Chúng ta tìm đồ thị ở đâu?

Đồ thị ở khắp mọi nơi xung quanh chúng ta. Bất cứ nơi nào chúng tôi cố gắng tìm một liên kết giữa hai đối tượng, cấu trúc dữ liệu biểu đồ sẽ xuất hiện trong bức tranh. Nếu chúng ta lấy ví dụ về Facebook, tất cả bạn bè của chúng ta đều có kết nối trực tiếp với chúng ta. Giả sử người A có tình bạn với người B. Bây giờ, nếu chúng ta biểu diễn điều này dưới dạng đồ thị, A và B là hai đỉnh hoặc nút có cạnh giữa chúng. Tương tự, nếu A cũng là bạn của C và B không biết C, biểu đồ sẽ như thế này -

Nếu các mạng xã hội có lẽ là ví dụ được sử dụng nhiều nhất để mô tả các biểu đồ xung quanh chúng ta, thì ví dụ phổ biến thứ hai có thể là các phân tử - đặc biệt là các phân tử hữu cơ giống như protein. Một loạt các hoạt động đồ thị có thể được thử nghiệm trên các cấu trúc protein phức tạp này. Ví dụ cuối cùng nhưng không kém phần quan trọng về biểu đồ là kết nối giữa các thiết bị đầu cuối trong mạng viễn thông.

Sức mạnh của biểu đồ không chỉ phân tích các thuộc tính của các nút của nó. Biểu đồ cũng thể hiện sự tương tác giữa các nút đó. Với sự tiến bộ của mạng xã hội, viễn thông, internet, v.v., chúng tôi đang nhận được một lượng dữ liệu đồ thị dồi dào để phân tích và hiểu. Thách thức của chúng tôi là khai thác tiềm năng to lớn của lượng dữ liệu khổng lồ này.

Đồ thị là gì?

Trước khi đi sâu, chúng ta nên hiểu rõ về cấu trúc dữ liệu đồ thị. Hãy xác định một biểu đồ:

= (, ℰ)

trong đó đại diện cho các đỉnh hoặc nút và ℰ đại diện cho các cạnh của đồ thị. Không bắt buộc tất cả các nút phải có số cạnh bằng nhau hoặc thậm chí là bất kỳ cạnh nào. Một cạnh xác định sự tương tác hoặc mối quan hệ giữa các nút. Hãy xem xét việc ông Sharma ở nhà bên cạnh. Nếu tôi cố gắng biểu diễn xã hội nhà ở bằng một biểu đồ và tất cả các ngôi nhà là các nút, thì có thể có một cạnh được xác định giữa ông Sharma (màu đỏ) và tôi (màu xanh) và cạnh này có thể được đặt tên là is_neighbour_of . Vì vậy, ông Sharma là_hàng xóm_của tôi . Bây giờ, thực tế ông Sharma không phải là hàng xóm duy nhất của tôi. Ở phía bên kia, tôi có ông Sen (màu cam) và ông Venkatesh (màu xanh lá cây) ở ngay đối diện nhà tôi. Vì vậy, tôi thực sự kết nối với cả ba người này với mộtmối quan hệ is_neighbour_of . Nhưng không ai trong số họ là hàng xóm của người kia (nếu tôi định nghĩa hàng xóm chỉ là nhà bên cạnh - xã hội khá khó xử nhỉ?).

Bây giờ Nếu chúng ta muốn xem mối quan hệ ở dạng bảng, ma trận sau đây với có cho hàng xóm và không cho hàng xóm không có thể hữu ích -

Đây được gọi là ma trận kề của đồ thị. Không giống như ví dụ này, tất cả các cạnh trong biểu đồ có thể không giống nhau. Nếu nhà của ông Sharma xa hơn so với nhà của ông Sen, thì tôi sẽ có cơ hội gặp ông Sen thường xuyên hơn ông Sharma. Vì vậy, tầm quan trọng (hoặc trọng lượng) của lợi thế giữa tôi và ông Sen mạnh hơn so với ông Sharma. Trọng lượng cạnh đóng một vai trò quan trọng trong nhiều trường hợp.

Các loại biểu đồ khác nhau

Có ba loại đồ thị cơ bản — vô hướng, có hướng và có trọng số.

Hình trên mô tả từng cái trong số ba cái này. Đối với đồ thị có hướng, nó chỉ cho phép di chuyển theo một hướng (từ màu xanh sang màu đỏ trong hình này). Nó giống như tình yêu đơn phương vậy. Mặt khác, đồ thị vô hướng giống như Mr Sharma và tôi. Cả hai chúng tôi đều là hàng xóm của nhau. Một biến thể nhỏ khác của đồ thị vô hướng là đồ thị hai chiều. Ví dụ: giả sử con gái của Anita là Megha, do đó, mẹ của Megha là Anita. Vì vậy, khi bạn coi chúng là hai nút của biểu đồ, nó sẽ trông giống như sơ đồ bên dưới -

Đây được gọi là đồ thị hai chiều.

Như tôi đã trích dẫn một ví dụ về biểu đồ có trọng số trong phần trước, trọng số cạnh đóng một vai trò quan trọng để ước tính độ bền của kết nối. Chúng ta sẽ thấy tầm quan trọng của nó ở phần sau.

Nếu ai đó muốn mở rộng ví dụ về đồ thị hai chiều để thiết lập một đồ thị họ, thì một loại đồ thị mới sẽ được xây dựng gọi là đồ thị đa quan hệ. Trong một gia đình luôn tồn tại những mối quan hệ khác nhau giữa mọi người với nhau nên sẽ có những kiểu cạnh khác nhau. Đồ thị đa quan hệ có hai dạng khác được gọi là đồ thị không đồng nhất và đồ thị ghép kênh.

Như tên gợi ý, một biểu đồ không đồng nhất bao gồm các loại nút khác nhau - chẳng hạn như thành viên nam và thành viên nữ trong gia đình. Mặt khác, một biểu đồ ghép kênh có thể là một biểu đồ được xây dựng bởi các thành phố khác nhau và các cạnh là các phương thức vận tải khác nhau. Hai thành phố bất kỳ có thể có nhiều phương thức vận chuyển (bằng đường sắt, đường hàng không hoặc đường bộ) được gọi là ' lớp ' của biểu đồ ghép kênh.

Trong phần tiếp theo, chúng ta sẽ tìm hiểu về các tính năng cấp độ nút, cạnh và biểu đồ.