- Giới thiệu về Mạng xã hội. - 10 1.1 Khái niệm Mạng xã hội. - 10 1.2 Sự phát triển của Mạng xã hội. - 17 CHƢƠNG 2: ỨNG DỤNG CỦA LÝ THUYẾT ĐỒ THỊ TRONG PHÂN TÍCH MẠNG XÃ HỘI. - 18 2.1 Lý thuyết đồ thị. - 18 2.1.1 Định nghĩa đồ thị. - 18 2.1.2 Biểu diễn mạng xã hội theo đồ thị. - 21 2.2 Cộng đồng trong mạng xã hội. - 23 2.3 Các kỹ thuật gom nhóm – phát hiện cộng đồng. - 45 Chƣơng 3: BÀI TOÁN CỘNG ĐỒNG HIẾM MUỘN. - 47 Học viên: Chu Quang Phổ -4- Luận văn thạc sĩ 3.1.2 Những vấn đề của các cặp hiếm muộn. - 48 3.2 Yêu cầu đối với mạng xã hội cộng đồng hiếm muộn. - 51 3.2.1 Forum Cộng đồng hiếm muộn. - 52 3.2.3 Phân nhóm cộng đồng. - 53 3.3.1 Forum cộng đồng hiếm muộn. - 54 3.3.3 Phân nhóm cộng đồng. - 2 CĐHM Cộng đồng hiếm muộn 3 CNTT Công nghệ thông tin 4 CEO Chief Executive Officer 5 WHO World Health Organization Học viên: Chu Quang Phổ -6- Luận văn thạc sĩ DANH MỤC HÌNH VẼ, BẢNG BIỂU Danh mục hình vẽ Hình 1 Thống kê số lƣợng truy cập vào ZingMe. - 12 Hình 2 Đơn đồ thị vô hƣớng. - 19 Hình 3 Đa đồ thị vô hƣớng. - 19 Hình 4 Giả đồ thị vô hƣớng. - 20 Hình 5 Đơn đồ thị vô hƣớng. - 20 Hình 6 Đa đồ thị có hƣớng. - 21 Hình 7 Biểu diễn mạng xã hội theo đồ thị. - 22 Hình 8 Ví dụ về một đồ thị với 3 cộng đồng. - 23 Hình 9 Đồ thị vô hƣớng 7 đỉnh. - 30 Hình 11 Đồ thị 6 đỉnh. - 31 Hình 12 Đồ thị gồm 6 đỉnh. - 35 Hình 13 Đồ thị 7 đỉnh. - 38 Hình 14 Ví dụ về phát hiện cộng đồng theo thuật toán Newman-Girvan. - 45 Hình 17 Mô hình hệ thống MXH Cộng đồng hiếm muộn. - Bởi mục đích xây dựng trang MXH cộng đồng hiếm muộn cần: tính đơn giản khi xây dựng, có diễn đàn, và các tính năng của một trang MXH. - Hoàn thành đƣợc tính năng gợi ý kết bạn trên trang Cộng đồng hiếm muộn - Đƣa ra lý thuyết đã đƣợc áp dụng cho việc phân nhóm cộng đồng. - Trong việc phân tích mạng xã hội bản chất là chúng ta đi tìm các điểm chung của các thực thể để xác định và phân chia các thực thể đó và các nhóm hay chính là cộng đồng trong mạng xã hội đó. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -19- Luận văn thạc sĩ Hình 2 Đơn đồ thị vô hƣớng Đa đồ thị vô hƣớng Đa đồ thị vô hƣớng G = bao gồm V là tập các đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. - Hình 3 Đa đồ thị vô hƣớng Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -20- Luận văn thạc sĩ Giả đồ thị vô hƣớng Giả đồ thị vô hƣớng G = bao gồm V là tập đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử (hai phần tử không nhất thiết phải khác nhau) trong V đƣợc gọi là các cạnh. - Hình 5 Đơn đồ thị vô hƣớng Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -21- Luận văn thạc sĩ Đa đồ thị có hƣớng Đa đồ thị có hƣớng G = bao gồm V là tập đỉnh, E là cặp có thứ tự gồm hai phần tử của V đƣợc gọi là các cung. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -22- Luận văn thạc sĩ Trong biểu diễn đồ thị của mạng xã hội, các đỉnh đƣợc dùng để biểu diễn các nút và các cạnh dùng để biểu diễn liên kết giữa các nút. - Một cộng đồng là một nhóm xã hội của các cơ thể sống chung trong cùng một môi trƣờng thƣờng là có cùng các mối quan tâm chung. - Cộng đồng đƣợc hình thành trên cơ sở các mối liên hệ giữa cá nhân và tập thể dựa trên cơ sở tình cảm là chủ yếu, ngoài ra còn có các mối liên Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -23- Luận văn thạc sĩ hệ tình cảm khác. - Việc phát hiện cộng đồng có rất nhiều ứng dụng cụ thể. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -25- Luận văn thạc sĩ Một khía cạnh quan trọng khác nữa trong cấu trúc cộng đồng là cách tổ chức phân cấp, cách tổ chức này có thể nhìn thấy trong hầu hết các mạng xã hội trong thực tế. - Riêng trong lĩnh vực khai phá dữ liệu, bài toán khai phá cộng đồng trong mạng xã hội cũng có một ứng dụng tƣơng đối rộng rãi. - Khai phá cộng đồng ứng dụng trực tiếp vào các bài toán chính của khai phá dữ liệu nhƣ nhận dạng thực thể, phân cụm, xếp hạng thực thể hay phân lớp thực thể, dự đoán các liên kết hay phát hiện các đồ thị con…, trong đó các nhà khoa học quan tâm nhất đến phân cụm thực thể và xếp hạng các thực thể có liên quan đến nhau trong các Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -26- Luận văn thạc sĩ cụm vừa đƣợc phân. - Trong y học các bệnh nhân của một nhóm bệnh có thể coi là một cộng đồng. - Họ có thể chia sẻ các thông tin, kinh nghiệm đã từng trải qua cho các thành viên trong cộng đồng. - 2.3 Các kỹ thuật gom nhóm – phát hiện cộng đồng Hiện nay có nhiều phƣơng pháp, kỹ thuật gom nhóm và phát hiện cộng đồng trong mạng xã hội. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -27- Luận văn thạc sĩ 2.3.1.1 Độ đo trung tâm theo bậc - Degree Centrality - Khái niệm Cho đồ thị G(v,e) có n đỉnh. - o n là số đỉnh của đồ thị. - H ay nó i cách khác thì độ đo trung tâm dựa và trung gian là độ đo dùng để xác định vị trí của tác Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -29- Luận văn thạc sĩ nhân trong mạng mà nó có khả năng kết nối đến những cặp tác nhân hay những nhóm tác nhân khác. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -30- Luận văn thạc sĩ o Nếu đỉnh này bị loại bỏ thì sẽ gây ra sự tan rã cấu trúc của mạng, tức là các đỉnh sẽ không còn có thể trao đổi thông tin liên lạc với nhau. - Đồ thị đƣợc biểu diễn nhƣ sau: Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -31- Luận văn thạc sĩ Hình 11 Đồ thị 6 đỉnh Áp dụng công thức toán độ đo trung theo trung gian ta có tìm đƣợc tất cả các đƣờng đi ngắn nhất của tất cả các cặp đỉnh trong mạng: Shortest Path (s,t) Path Length SP Length(SP(1,2))=1 SP Length(SP(1,3))=1 SP . - Nhƣ vậy st ( v1) 0 Xét đỉnh v2: ta thấy có 3 đƣờng đi có đi qua đỉnh v2, vậy st ( v2 ) 3 Xét đỉnh v3: ta thấy có 3 đƣờng đi có đi qua đỉnh v3, vậy st ( v3 ) 3 Xét đỉnh v4: ta thấy có 8 đƣờng đi có đi qua đỉnh v4, vậy st ( v4) 8 Xét đỉnh v5 và v6: ta không thấy có bất kỳ đƣờng đi nào đi qua 2 đỉnh này, nhƣ vậy st ( v5) 0 và st ( v6) 0 Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -33- Luận văn thạc sĩ Nhƣ vậy: Dựa vào các độ đo Betweenness Centrality của từng đỉnh ở trên ta thấy đỉnh v4 có độ đo cao nhất đồng nghĩa với việc đỉnh v4 này là đỉnh có tầm ảnh hƣởng cao nhất đối với các đỉnh khác. - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -34- Luận văn thạc sĩ Giá trị các độ đo Betweenness Centrality của từng đỉnh trong đồ thị Sau khi loại bỏ đỉnh v4 (đỉnh có độ đo CB(v4. - 1 o Xét đỉnh 2 trong đồ thị. - 2 Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -39- Luận văn thạc sĩ o Xét đỉnh 3 trong đồ thị. - 2 o Xét đỉnh 5 trong đồ thị. - Thuật toán dựa trên quan điểm cho rằng Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -40- Luận văn thạc sĩ khi các cộng đồng đƣợc gắn kết với nhau thì đƣờng đi giữa cộng đồng này đến cộng đồng khác sẽ đi qua các cạnh nối giữa các cộng đồng với tần suất cao. - Khi đó, các cộng đồng trong mạng sẽ bị phân chia với nhau, ta có thể xác định đƣợc cách phân vùng đồ thị thành các phần nhỏ riêng rẽ. - Ví dụ với một mạng đƣợc liên kết với nhau nhƣ đồ thì bên dƣới: Hình 14 Ví dụ về phát hiện cộng đồng theo thuật toán Newman-Girvan Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -41- Luận văn thạc sĩ Sau khi thực hiện loại bỏ các cạnh nối màu xanh là các cạnh có đọ trung gian cao nhất ta sẽ thu đƣợc 3 cộng đồng độc lập nhƣ hình 14 bên trên. - Tổng thời gian chạy là O(m2n), trong trƣờng hợp xấu nhất của thuật toán là O(n3) với mỗi đỉnh là một cộng đồng. - Phép chia các đỉnh này là phù hợp với ý tƣởng của thuật toán Girvan- Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -42- Luận văn thạc sĩ Newman bởi vì , cũng nhƣ việc loại bỏ các cạnh, việc phân chia các đỉnh cũng có thể làm cho một cộng đồng lớn chia thành các cộng đồng con. - Để tính toán độ trung gian phép phân chia của đỉnh v, ta sử dụng một độ đo khác là độ trung gian theo cặp của v theo (u,w).Giả sử u, w là hai đỉnh kề bất Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -44- Luận văn thạc sĩ kỳ của v, độ trung gian theo cặp của v theo (u,w) chính là số đƣờng đi ngắn nhất của bất kỳ cặp đỉnh trong đồ thị mà đi qua (u,v) và (v,w). - Chương 2: ứng dụng của lý thuyết đồ thị trong phân tích mạng xã hội Học viên: Chu Quang Phổ -45- Luận văn thạc sĩ Nhƣ vậy, thuật toán này có ƣu điểm là giải quyết đƣợc vấn đề chồng chéo cộng đồng bằng cách đặt ra phép phân chia đỉnh, ngoài ra nội dung thuật toán tƣơng đối dễ hiểu và xác định đƣợc phép phân chia tối ƣu nhất trong các trƣờng hợp, một điều mà thuật toán Girvan-Newman nguyên thủy không làm đƣợc. - Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -47- Luận văn thạc sĩ Chƣơng 3: BÀI TOÁN CỘNG ĐỒNG HIẾM MUỘN 3.1. - Tuy nhiên đáng lo nhất là tình trạng quan hệ tình dục thiếu Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -48- Luận văn thạc sĩ an toàn dẫn tới nhiều phụ nữ bị viêm nhiễm đƣờng sinh dục, nạo hút thai, sảy thai, có thai ngoài tử cung. - Các cặp hiếm muộn đa phần không phải gia đình nà cũng có điều Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -49- Luận văn thạc sĩ kiện về tài chính nhiều nên khi chữa trị tài chính cũng là một vấn đề lớn mà các cặp hiếm muộn gặp phải. - Khi ngƣời con trai út cƣới vợ đƣợc hơn một năm mà hai vợ chồng vẫ chƣa có con cả gia đình đều động Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -50- Luận văn thạc sĩ viên cả hai vợ chồng đi khám. - Do đó tôi muốn góp một phần nhỏ bé công sức của mình vào để phát triển một cộng đồng dành riêng cho các cặp Hiêm muộn và tôi quyết định xây dựng mạng xã hội Cộng đồng hiếm muộn. - Kế hoạch xây dựng Mạng xã hội Cộng đồng hiếm muộn: Xây dựng mạng xã hội cồng đồng hiếm muộn dựa vào bộ Open source PHPFOX. - Xây dựng mối quan hệ giữa các thành viên trong mạng xã hội. - Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -51- Luận văn thạc sĩ Phân nhóm các thành viên trong mạng vào các nhóm. - 3.2 Yêu cầu đối với mạng xã hội cộng đồng hiếm muộn Nhƣ đã nêu ở phần phát biểu bài toán, mục đich của cộng đồng hiếm muộn khi xây dựng lên với mục đích hoàn thiện đƣợc các tính năng chính nhƣ sau: Tạo đƣợc một diễn đàn chia sẻ thông tin dành riêng cho các cặp hiếm muộn. - Từ tập các thành viên của mạng sau khi phát triển cộng đồng cần phân nhóm các thành viên. - Đối tƣợng đƣợc diễn đàn cộng đồng hiếm muộn đƣợc phân loại theo giới tính là: Nam và nữ. - Vô sinh nguyên phát là các trƣờng hợp vợ chồng lấy nhau từ 1 năm trở lên quan hệ bình thƣờng không dùng các biện pháp Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -52- Luận văn thạc sĩ tránh thai nào mà vẫn chƣa có con. - 3.2.2 Giới thiệu kết bạn Bên cạnh việc tạo ra diễn đàn chia sẻ thì mạng xã hội cộng đồng hiếm muộn cần có sự kết nối giữa các thành viên. - Cần có sự lƣu trữ các thông tin mà Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -53- Luận văn thạc sĩ thành viên của cộng đồng hiếm muộn quan tâm dựa vào các mục bài viết mà họ thƣờng xuyên theo dõi. - 3.2.3 Phân nhóm cộng đồng Với các thành viên trong mạng xã hội Cộng đồng hiếm muộn khi có mối quan tâm giống nhau, kết bạn với nhau thì ta cần phải phân nhóm đƣợc các đối tƣợng thành viên này vào thành các nhóm hay tách nhỏ cộng đồng hiếm muộn nói chung thành các cộng đồng nhỏ hơn. - Kỹ thuật mới nhất đƣợc áp dụng trong việc điều trị hiếm muộn: đƣa ra các kết quả nghiên cứu mới nhất về các phƣơng pháp điều trị hiếm muộn đã đạt đƣợc Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -54- Luận văn thạc sĩ trên thế giới hiện nay và các phƣơng pháp điều trị đang đƣợc áp dụng tại Việt Nam. - Ví dụ nhƣ một thành viên của Mạng xã hội cộng đồng hiếm muộn khi tham gia vào mạng hay quan tâm tới các bài viết vô sinh nam thứ phát. - Sau đó ta sẽ có đƣợc danh sách các thành viên và số lần thành viên truy Chương 3: Bài toán Cộng đồng hiếm muộn Học viên: Chu Quang Phổ -55- Luận văn thạc sĩ cập vào các chuyên mục. - 3.3.3 Phân nhóm cộng đồng Không giống với các mạng xã hội đang phổ biến hiện nay nhƣ Facebook, Twitter, Google Plus… là chúng ta phải dựa trên các thông tin mối quan hệ, sự quan các thành viên để xác định ra đƣợc các cộng đồng. - Vì vậy cần có các thuật toán để phát hiện cộng đồng trong mạng xã hội. - Ứng với mạng xã hội cộng đồng hiếm muộn là mạng xã hội đƣợc phát triển dành riêng cho nhóm đối tƣợng là các trƣờng hợp hiếm muộn. - Cộng đồng hiếm muộn nam do nguyên nhân thứ phát. - Cộng đồng hiếm muộn nữ do nguyên nhân nguyên phát. - Cộng đồng hiếm muộn nữ do nguyên nhân thứ phát. - Xây dựng Forum Với lựa chọn sử dụng gói mã nguồn mở PHPFOX để xây dựng trang cộng đồng hiếm muộn thì việc tạo Forum đã đƣợc PhpFox hỗ trợ. - Với việc hỗ trợ này ta có thể dễ dàng tạo đƣợc diễn đàn cộng đồng hiếm muộn với các yêu cầu đặt ra. - Kết quả của việc hỗ trợ này là chúng ta đã xây dựng đƣợc các chuyên mục của diễn đàn cộng đồng hiếm muộn theo mong muốn. - Nêu lên đƣợc nhu cầu cần thiết xây dựng mạng xã hội cộng đồng hiếm muộn cho các trƣờng hợp hiếm muộn gặp phải. - Thực hiện đƣợc việc đƣa ứng dụng mạng xã hội “Cộng đồng hiếm muộn” lên internet theo địa chỉ: congdonghiemmuon.vn Hoàn thiện đƣợc tính năng chuyên mục của diễn đàn cộng đồng hiếm muộn. - Xây dựng đƣợc tính năng gợi ý kết bạn cho các thành viên trong mạng Cộng đồng hiếm muộn. - Chỉ ra đƣợc cơ sở lý thuyết đã đƣợc công bố cho việc phân nhóm cộng đồng. - Những điều chƣa thực hiện đƣợc: Chƣa áp dụng đƣợc lý thuyết việc phân nhóm cộng đồng vào mạng xã hội cộng đồng hiếm muộn. - Điều này do nguyên nhân là hiện tại mạng xã hội cộng đồng hiếm muộn đang trong giai đoạn phát triển và chạy thử nghiện, chƣa đƣợc đƣa lên internet và chƣa có thành viên làm đối tƣợng phân tích. - Hƣớng phát triển thời gian tới: Chương 5: Kết luận Học viên: Chu Quang Phổ -69- Luận văn thạc sĩ Giai đoạn 1: Phát triển cộng đồng để mọi ngƣời biết đến trang congdonghiemmuon.vn. - Giai đoạn 3: Cần áp dụng lý thuyết phân nhóm cộng đồng trong đề tài này vào việc phân nhóm các thành viên trong mạng xã hội cộng đồng hiếm muộn. - Phụ lục Học viên: Chu Quang Phổ -70- Luận văn thạc sĩ TÀI LIỆU THAM KHẢO [1] Vũ Thị Thu Hƣơng (2012), Phát hiện cộng đồng và sử dụng thuật toán CONGA và khai phá quan điểm cộng đồng trên mạng xã hội. - [5] Tr ần Trung Hiếu (2011), Họ thuật toán Girvan – Newman trong phát hiện cộng đồng và cài đặt thử nghiệm trên mạng xã hội trực tuyến
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt