Một mô hình tìm kiếm vai trò trong mạng xã hội Twitter

  • Số trang: 56 |
  • Loại file: PDF |
  • Lượt xem: 24 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27679 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐINH THỊ HƢƠNG MỘT MÔ HÌNH TÌM KIẾM VAI TRÒ TRONG MẠNG XÃ HỘI TWITTER Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã Số: 60480104 LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2014 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐINH THỊ HƢƠNG MỘT MÔ HÌNH TÌM KIẾM VAI TRÒ TRONG MẠNG XÃ HỘI TWITTER Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã Số: 60480104 LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HÀ QUANG THỤY HÀ NỘI - 2014 2 Lời cam đoan Tôi xin cam đoan luận văn “Một mô hình tìm kiếm vai trò trong mạng xã hội Twitter" là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận văn là hoàn toàn trung thực. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan. Ngoại trừ các tài liệu tham khảo này, luận văn hoàn toàn là công việc của riêng tôi. Luận văn được hoàn thành trong thời gian tôi là học viên tại Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Hà Nội, ngày 25 tháng 10 năm 2014 Học viên Đinh Thị Hƣơng 3 Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới PGS.TS. Hà Quang Thụy cùng Phòng Thí nghiệm KTLab đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Luận văn này được thực hiện trong khuôn khổ đề tài mã số BB-2012-B42-29 của Bộ Công an. Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để tôi học tập và nghiên cứu tại trường Đại học Công Nghệ. Tôi xin gửi lời cảm ơn tới các bạn trong lớp cao học K18 đã ủng hộ, khuyến khích tôi trong suốt quá trình học tập tại trường. Cuối cùng, tôi muốn được gửi lời cảm ơn vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin chân thành cảm ơn! Hà Nội, ngày 25 tháng 10 năm 2014 Học viên Đinh Thị Hƣơng 4 Tóm tắt nội dung Phát hiện vai trò trên mạng xã hội trực tuyến không chỉ gây được sự chú ý bởi giới học thuật mà còn trong cả giới kinh doanh. Đối với các nhà đầu tư, doanh nghiệp, việc quảng bá sản phẩm, thương hiệu dựa trên vai trò của những người có ảnh hưởng lớn trong mạng xã hội mang lại hiệu quả kinh tế cao. Những nhận định, đánh giá hay khen, chê về một sản phẩm, mặt hàng của những người có vai trò quyết định trong mạng xã hội sẽ được đông đảo người dùng trong mạng dõi theo và có thể bị ảnh hưởng bởi những nhận định, đánh giá đó. Các nghiên cứu gần đây cũng chứng minh được rằng các vai trò quan trọng trong mạng xã hội có ảnh hưởng lớn đến quyết định mua sắm, ăn uống, tiêu dùng, hoạt động chính trị, biểu tình, bầu cử… của những người dùng khác trong mạng. Chính vì lẽ đó mà nhu cầu tìm kiếm, phát hiện vai trò trong mạng xã hội ngày càng tăng cao. Luận văn tập trung nghiên cứu một mô hình tìm kiếm vai trò trong mạng xã hội Twitter và thực nghiệm tìm kiếm 3 vai trò: người nổi tiếng, người vận động quảng bá, người khởi tạo ý tưởng trong truyền tin. Luận văn đề nghị một mô hình tìm kiếm ba vai trò trên với một số biến thể từ mô hình của Vanesa Junquero-Trabado và cộng sự [21]: (i) bổ sung đặc trưng số lượng retweet của người dùng; (ii) sử dụng thuật toán K-mean suy rộng [10] thay vì sử dụng thuật toán K-mean; (iii) sử dụng phương án chuẩn hóa tốt nhất (chuẩn hóa Max/Min) mà không xem xét các phương án khác; (iv) không thực hiện mở rộng tập mồi (seed) sau khi gán vai trò. Luận văn thi hành phần mềm thử nghiệm mô hình và tiến hành thực nghiệm trên bộ dữ liệu tại Đại học Stanford. Kết quả thực nghiệm cho độ đo F-measure trung bình là 81.1%. Kết quả trên cho thấy phương pháp tìm kiếm vai trò trong mạng xã hội Twitter được luận văn đề xuất và triển khai là khả quan, có khả năng ứng dụng trong thực tế. 5 Mở đầu Trong những năm gần đây, mạng xã hội trực tuyến (online social networks: OSNs) phản ánh ngày càng phong phú đời sống xã hội và tinh thần trong xã hội loài người và khai phá dữ liệu OSNs đã trở thành lĩnh vực khoa học và công nghệ nổi bật [11] thu hút sự quan tâm đặc biệt của nhiều tổ chức, nhiều nhóm nghiên cứu trên thế giới, chẳng hạn dãy hội nghị hàng năm TREC tại Viện chuẩn và khoa học Mỹ [microblog-track]. Khai phá, phát hiện vai trò trong mạng xã hội Twitter là nội dung nghiên cứu, làm rõ mô hình toán học cho sự tương tác, vai trò giữa mọi người, các tổ chức và các nhóm với nhau trong việc phân tích mạng xã hội Twitter [16, 15].Việc phát hiện, tìm kiếm vai trò nhận được sự quan tâm lớn của các nhà nghiên cứu, các nhà đầu tư, các doanh nghiệp, tổ chức chính trị. Lợi ích của việc tìm ra những vai trò có ảnh hưởng lớn trong mạng xã hội mang lại hiệu quả khá rõ ràng, các công ty, doanh nghiệp hay các nhà tiếp thị có thể dựa trên những vai trò có ảnh hưởng lớn trên mạng để quảng bá thương hiệu, sản phẩm đến khách hàng, người tiêu dùng. Nó như một công cụ thông tin giúp các nhà doanh nghiệp có thể giao tiếp với những người quan tâm đến sản phẩm hoặc làm cho thương hiệu của các nhà doanh nghiệp đó trở nên quen thuộc với những người chưa biết. Luận văn này tiến hành nghiên cứu các phương pháp phát hiện vai trò trong mạng xã hội Twitter bao gồm khảo sát các mô hình phân tích mạng xã hội và các mô hình phát hiện vai trò điển hình. Từ đó đề xuất một mô hình tìm kiếm vai trò trong mạng xã hội Twitter. Một vai trò xã hội được định nghĩa như một tập hợp những đặc tính mô tả cách hành xử của mỗi cá nhân và mối liên hệ giữa họ trong một ngữ cảnh nhất định. Trong mô hình này, chúng tôi thực hiện trích chọn các đặc trưng của một người trong mạng xã hội, tiếp theo sử dụng 1 thuật toán phân cụm để phân cụm những người có những đặc trưng tương đồng vào cùng một cụm. Đối với vai trò cần tìm kiếm sẽ có một tập các độ đo phù hợp tương ứng với vai trò đó. Từ những độ đo phù hợp này, chúng tôi sẽ tìm kiếm các cụm dữ liệu mà có các đặc trưng tương đồng với độ đo trên và trả về kết quả. Luận văn đã thực nghiệm mô hình với kết quả đạt được khá khả quan so với kết quả của thế giới. Nội dung của luận văn được chia thành các chương như sau: 6 Chƣơng 1: Luận văn giới thiệu khái quát về mạng xã hội, mạng xã hội Twitter, bài toán phát hiện vai trò trong mạng xã hội. Chƣơng 2: Luận văn đưa ra một số nghiên cứu liên quan về việc phát hiện vai trò trong mạng xã hội nói chung và mạng xã hội Twitter nói riêng. Đồng thời trong chương này cũng trình bày một thuật toán phân cụm hiệu quả để cải thiện kết quả của bài toán. Chƣơng 3: Luận văn đề xuất một mô hình tìm kiếm vai trò trên mạng xã hội Twitter. Tư tưởng chính của mô hình sẽ được thể hiện trong chương này. Đồng thời, luận văn cũng trình bày chi tiết các pha cũng như những các bước thực hiện trong mô hình. Chƣơng 4: Thực nghiệm, kết quả và đánh giá. Tiến hành thực nghiệm theo mô hình đã đề xuất trong chương 4. Phần kết luận: Tóm lược kết quả đạt được của luận văn và định hướng phát triển tương lai. 7 Mục Lục Lời cam đoan ................................................................................................................... 3 Lời cảm ơn ....................................................................................................................... 4 Tóm tắt nội dung.............................................................................................................. 5 Mở đầu ............................................................................................................................. 6 Mục Lục ........................................................................................................................... 8 Danh mục hình vẽ .......................................................... Error! Bookmark not defined. Danh mục bảng biểu ...................................................... Error! Bookmark not defined. Danh mục viết tắt ........................................................................................................... 12 1. Chương 1. Giới thiệu về mạng xã hội, mạng xã hội Twitter và bài toán khai phá vai trò trong mạng xã hội .................................................................................................... 13 1.1 Giới thiệu về mạng xã hội ................................................................................ 13 1.1.1 Sự phát triển của mạng xã hội ....................................................................... 13 1.1.2 Khái niệm mạng xã hội ................................................................................. 15 1.2 Giới thiệu về mạng xã hội Twitter .................................................................. 16 1.3 Bài toán khai phá vai trò trong mạng xã hội .................................................... 18 2.Chương 2. Các phương pháp phát hiện vai trò trong mạng xã hội và một số thuật toán phân cụm........................................................................................................................ 20 2.1. Các phương pháp phát hiện vai trò trong mạng xã hội ....................................... 20 2.2. Một kiến trúc tìm kiếm vai trò trong mạng xã hội áp dụng trên miền dữ liệu Twitter của Vanesa Junquero Trabado và cộng sự [21]............................................. 21 2.3. Một mô hình phát hiện vai trò truyền tin trong Twitter ...................................... 29 2.4. Một thuật toán phân cụm cải tiến K-mean .......................................................... 30 3.Chương 3. Mô hình đề xuất tìm kiếm vai trò trong mạng xã hội Twitter .................. 36 3.1. Tư tưởng chính của mô hình ............................................................................... 36 3.2. Mô hình đề xuất .................................................................................................. 37 3.2.1. Pha phân tích đặc trưng ................................................................................ 38 3.2.2 Pha phân cụm dữ liệu .................................................................................... 40 8 3.2.3 Pha gán vai trò .............................................................................................. 40 4.Chương 4. Thực nghiêm và đánh giá ......................................................................... 43 4.1. Môi trường và các công cụ sử dụng thực nghiệm ............................................... 43 4.2. Tập dữ liệu thử nghiệm ....................................................................................... 44 4.3. Thực nghiệm ....................................................................................................... 45 4.3.1 Phân tích đặc trưng ........................................................................................ 45 4.3.2 Pha phân cụm dữ liệu .................................................................................... 50 4.3.3 Pha gán vai trò ............................................................................................... 50 4.4 Kết quả thử nghiệm và phương pháp đánh giá .................................................... 51 Kết luận.......................................................................................................................... 53 Tài liệu tham khảo ......................................................................................................... 54 9 Danh mục hình vẽ Hình 1: Một ví dụ về sociogram .................................................................................... 13 Hình 2: Một ví dụ về thuật ngữ Twitter ........................................................................ 17 Hình 3: Mô hình thực thế quan hệ ................................................................................. 23 Hình 4: Một ví dụ về gán vai trò ................................................................................... 26 Hình 5: Kết quả đánh giá mô hình của Trabado và cộng sự [21].................................. 28 Hình 6: Giải thuật Lọc ................................................................................................... 34 Hình 7: Mô hình đề xuất ................................................................................................ 38 Hình 8: Phân bố giá trị độ đo đặc trưng M1 .................................................................. 46 Hình 9: Phân bố giá trị độ đo đặc trưng M2 ................................................................. 46 Hình 10: Phân bổ giá trị độ đo đặc trưng M3 ................................................................ 47 Hình 11: Phân bố giá trị độ đo đặc trưng M8 ................................................................ 48 Hình 12: Phân bổ giá trị đọ đo đặc trưng M9 ................................................................ 48 Hình 13: Phân bố giá trị độ đo đặc trưng M10 ............................................................. 49 Hình 14: Phân bố giá trị độ đo đặc trưng M11 .............................................................. 49 Hình 15: Phân bố giá trị độ đo đặc trưng M15 .............................................................. 50 Hình 16: Kết quả đánh giá ............................................................................................. 52 10 Danh mục bảng biểu Bảng 1: Cấu hình phần cứng ......................................................................................... 43 Bảng 2: Các phần mềm sử dụng .................................................................................... 43 Bảng 3: Kết quả tìm kiếm .............................................................................................. 51 Bảng 4: Kết quả các thuật toán phân cụm ..................................................................... 51 11 Danh mục viết tắt STT Thuật ngữ Viết tắt 1 Chuẩn hóa Max/Min Max/Min 2 Chuẩn hóa Logarit Log 3 Chuẩn hóa xếp hạng Ranking 4 Chuẩn hóa điểm chuẩn Score 5 Độ lệch chuẩn –Standard Deviation Sdv 6 Lựa chọn giá trị lớn nhất MV 7 Lựa chọn giá trị lớn nhất trên hệ trục MVA 8 Tính toán giá trị trung bình Avg 9 Quá trình gia tăng Incr 12 Chƣơng 1. Giới thiệu về mạng xã hội, mạng xã hội Twitter và bài toán khai phá vai trò trong mạng xã hội 1.1 Giới thiệu về mạng xã hội 1.1.1 Sự phát triển của mạng xã hội Jiyang Chen, 2010 [2] đã đưa ra một giới thiệu khái quát về sự phát triển của quá trình nghiên cứu về mạng xã hội (social network). Nhu cầu phân tích mạng xã hội được bắt đầu từ những năm 1930 và nhanh chóng trở thành chủ đề quan trọng nhất trong xã hội học. Những người đi tiên phong trong lĩnh vực này là Jacob Moreno, Kurt Lewin và Fritz Heider. J.Moreno xây dựng một mô hình đặt tên là “sociometry” bằng cách hỏi những người xung quanh bạn của họ là ai, và tìm hiểu mối quan hệ của họ với những người khác. Sáng tạo của Moreno là ông đã tạo ra được một “sociogram”, một cách để biểu diễn các tính chất của một cấu hình mang tính xã hội. Khái niệm “sociogram” sau này cũng được dùng để chỉ biểu diễn đồ thị của các mạng xã hội. Hình 1: Một ví dụ về sociogram 13 Trong khi đó K.Lewin, trong một nghiên cứu về hành vi của các nhóm, cho rằng các tính chất về mặt cấu trúc của một đơn vị xã hội có thể biểu diễn một cách toán học bằng lý thuyết đồ thị và cấu trúc liên kết. Trong các nghiên cứu về nhận thức xã hội, F.Heider cũng phát minh ra thuyết cân bằng, trong đó ông cho rằng tâm trí con người luôn hướng tới sự cân bằng bằng cách giữ lại những ý tưởng mà không mâu thuẫn với ý tưởng của những người khác, điều này cũng được áp dụng vào trong thái độ với những người xung quanh mình. Những ý tưởng này của Lewin và Heider sớm được phát triển bởi Frank Harary và Dorwin Cartwright, trong đó nhóm tác giả sử dụng lý thuyết đồ thị để xây dựng một công cụ khá hữu hiệu trong nghiên cứu mạng xã hội Cũng theo [2], trong những năm 1950, các nhà nghiên cứu từ khoa Xã hội và Nhân chủng học của trường đại học Manchester, dẫn đầu là John Barnes, đã bắt đầu đặt trọng tâm nghiên cứu của họ vào các mối quan hệ giữa các đối tượng trong xã hội, thay vì thiết lập các chuẩn mực và định mức cho toàn bộ cấu trúc xã hội như trước; và tìm hiểu xem cấu trúc của các mối quan hệ giữa các cá thể trong xã hội có ảnh hưởng như thế nào đến toàn bộ xã hội. Từ đó, thuật ngữ “mạng xã hội”, lần đầu tiên được Barnes nhắc đến vào năm 1954, đã đánh dấu sự phát triển chính thức của việc phân tích cấu trúc mạng xã hội. Dựa vào các nghiên cứu của Barnes và các cộng sự, vào những năm 1969 và 1970, các nhà nghiên cứu ở đại học Harvard do Harrison C.White dẫn đầu tiếp tục nghiên cứu và phát triển các khía cạnh toán học của mạng xã hội và biểu diễn rất nhiều khái niệm quan trọng trong xã hội học, ví dụ như khái niệm “vai trò xã hội”, sang công thức toán học và tìm cách mô hình hóa và tính toán chúng. Ý tưởng chính của nghiên cứu là việc phát hiện cấu trúc của các mạng xã hội không nên dựa vào các hạng mục nổi tiếng và đã được định nghĩa trước đó, mà phải dựa vào mối quan hệ giữa các cá thể trong mạng và cách thức mà các mối quan hệ này cấu tạo thành mạng như thế nào. Trong một nghiên cứu sau đó, Mark Granovetter đề ra giả thiết liên kết yếu, với nội dung chính là “Nếu A có liên kết mạnh tới B và C thì rất có khả năng giữa B và C tồn tại một liên kết”. Giả thiết này của Granovetter được áp dụng tương đối hiệu quả trong một số nghiên cứu sau này. Tóm lại phân tích mạng xã hội [6] được sinh ra từ các nhu cầu chung của xã hội học, nhân chủng học, toán học, sinh học và kinh tế học. Ngày nay phân tích mạng xã hội còn được áp dụng trong nhiều lĩnh vực như kinh tế, tài chính…Tuy nhiên trong 14 thời đại bùng nổ thông tin hiện nay với số lượng và kích thước các mạng xã hội trực tuyến tăng lên không ngừng, các vấn đề về quản lý thông tin xã hội trở nên khó khăn hơn. Do đó, cần thiết phải áp dụng các kỹ thuật khoa học máy tính để phân tích chính xác và hiệu quả hơn các cấu trúc xã hội trên các mạng xã hội. 1.1.2 Khái niệm mạng xã hội Mạng xã hội là một cấu trúc mang tính xã hội được cấu tạo từ các nút và các cung, trong đó các nút được liên kết với nhau bởi một hoặc nhiều cung, thể hiện kiểu mối quan hệ cụ thể [2]. Mỗi nút, còn được gọi là một tác nhân (actor), biểu diễn cho một đối tượng trong xã hội, có thể là một người, một tài liệu, một tổ chức, một quốc gia… Liên kết giữa các nút được biểu diễn bởi một liên kết giữa các nút đó; liên kết này có thể là mối quan hệ bạn bè, họ hàng, đồng nghiệp,… cũng có thể là các trao đổi tài chính, các giao dịch, số liệu,… Các liên kết này có thể là liên kết vô hướng (hay còn gọi là liên kết đối xứng ), trong đó mối quan hệ giữa 2 nút A và B là mối quan hệ qua lại, ví dụ A là bạn B, và B cũng là bạn A, hay A và B cùng sống chung trong một căn hộ,… Các liên kết này cũng có thể là liên kết có hướng, ví dụ A thích B, nhưng B chưa chắc đã thích A, hay là A nợ tiền của B… Mặt khác, các liên kết còn có thể được đánh trọng số, trọng số này biểu diễn độ mạnh của liên kết đó giữa hai nút. Để biểu diễn mạng xã hội, các nhà phân tích mạng xã hội sử dụng hai cấu trúc phổ biến, đó là đồ thị và ma trận kề [11]. Để tính toán và phân tích các liên kết trong mạng, người ta thường ưu tiên áp dụng lý thuyết đồ thị do đồ thị là một trong những công cụ rất hữu hiệu để thể hiện các thông tin về mạng xã hội. 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. Các cạnh trong đồ thị có thể vô hướng hay có hướng, cũng có thể được đánh trọng số tùy thuộc vào nhu cầu biểu diễn liên kết xã hội là vô hướng hay có hướng, trọng số như thế nào. Mạng xã hội, cũng như các mạng trong thực tế khác thường có mức độ về mặt tổ chức và tính thứ tự cao. Mức độ của sự phân bố là rất rộng, với phần cuối thường theo một luật dạng lũy thừa, vì vậy, nhiều đỉnh ở mức thấp cùng tồn tại với một số đỉnh ở mức cao [7]. Hơn thế nữa, sự phân bố của các cạnh là không đồng đều không chỉ ở toàn thể mà còn ở mức cục bộ, với mức độ tập trung cao của các cạnh trong một số nhóm các đỉnh đặc biệt, và giữa các nhóm đó số lượng cạnh tập trung là thấp. Trong 15 biểu diễn đồ thị của các mạng xã hội, một số nhóm các đỉnh có liên kết chặt chẽ với nhau thành các cụm, và giữa các cụm đó được nối với nhau chỉ bằng một vài cạnh khác. 1.2 Giới thiệu về mạng xã hội Twitter Twitter là một trang web micro-blog được Twitter Inc. sở hữu và phát triển [5], cung cấp một dịch vụ mạng xã hội miễn phí cho phép người sử dụng gửi và nhận các tin nhắn gọi là Tweet. Twitter thực sự là mạng xã hội nhắn tin. Thành lập từ năm 2006, Twitter đã trở thành một hiện tượng phố biến toàn cầu. Giới hạn về độ dài của tin nhắn, 140 kí tự, có tính tương thích với tin SMS (Short Message Service), mang đến cho cộng đồng mạng một hình thức tốc ký đáng chú ý, đã được sử dụng rộng rãi đối với SMS. Hiện nay, Twitter đã đạt đến con số trên 500 triệu người sử dụng, với 65 triệu tweet được sinh ra mỗi ngày, và khoảng 800000 lượt truy vấn mỗi ngày. Twitter đôi khi còn được miêu tả như là “SMS trên Internet” Các thuật ngữ chính sử dụng trong Twitter: - Tweet: Những tin nhắn có độ dài tối đa 140 ký tự được gửi cho nhau và hiển thị trên profile cá nhân của mỗi người. ReTweet(RT):Cho phép người dùng chia sẻ lại những Tweet, liên kết từ những người dùng khác Mention (@): Sử dụng để tham chiếu đến một người khác bằng cách sử dụng tên đăng nhập của người đó trong Tweet (ví dụ @Mashable) Hashtag (#):Từ khóa của tài liệu. Hashtag là một công cụ khai phá cho phép những người khác tìm tweet của bạn dựa trên các chủ đề. Bạn có thể nhấp chuột vào 1 hashtag để xem tất cả các tweet đề cập đến chủ đề đó thậm chí cả những người bạn không theo dõi. - Following – Follower:Mối quan hệ theo dõi và được theo dõi. Dưới đây là một ví dụ về các thuật ngữ trên Twitter: 16 Hình 2: Một ví dụ về thuật ngữ Twitter Cũng như các mạng xã hội khác, Twitter có thể biểu diễn dưới dạng mô hình đồ thị, trong đó mỗi người sử dụng trực tuyến như là một đỉnh trong đồ thị, và các cạnh nối giữa các đỉnh thể hiện một mối quan hệ nào đó giữa 2 người sử dụng, chẳng hạn như mối quan hệ bạn bè. Mạng xã hội Twitter được ứng dụng rộng rãi trong việc xây dựng mô hình mạng xã hội, vì tính phổ biến cũng như quy mô rộng rãi của mạng xã hội này [30]. Twitter là một công cụ micro-blog phổ biến được xã hội yêu thích nhờ tính phổ biến và khả năng lan truyền nhanh trong các phương tiện truyền thông công cộng. Ví dụ như nó đã được sử dụng bởi các chiến dịch chính trị, tin tức tổ chức và cho truyền thông doanh nghiệp. Tổng thống Mỹ đương nhiệm Obama đã sử dụng rất tích cực và hiệu quả công cụ này khi ông chiến thắng trong cuộc chạy đua vào nhà trắng. Twitter cũng được các tạp chí hay các ngôi sao điện ảnh, ca sĩ, người nổi tiếng rất chuộng sử dụng để kết nối với khán giả và người hâm mộ. Mạng xã hội trực tuyến Twitter cho thấy khả năng phục vụ điều tra xã hội [3] vì vậy thu hút sự quan tâm đặc biệt của nhiều tổ chức, nhiều nhóm nghiên cứu trên thế giới, chẳng hạn dãy hội nghị hàng năm TREC tại Viện chuẩn và khoa học Mỹ [microblog-track]. 17 1.3 Bài toán phát hiện vai trò trong mạng xã hội Sự phát triển bùng nổ số lượng người tham gia vào các mạng xã hội làm tăng lên nhu cầu tìm hiểu những mẫu đặc trưng quan hệ tương tác giữa các người dùng. Một trong những hướng tiếp cận thông minh để tìm hiểu ai là ai trong mạng xã hội chính là phân loại người dùng theo vai trò của họ trong mạng. Hành động của các cá nhân trên mạng không mang tính ngẫu nhiên bởi mỗi người thường lặp lại những mẫu hành động mà thông qua đó xác định đựơc vai trò của họ trong một ngữ cảnh nhất định. Vai trò xã hội là thuật ngữ phổ biến được nghiên cứu bởi các nhà xã hội học. Trong lý thuyết vai trò, nó đựơc định nghĩa là những đặc tính của một hay một nhóm người trong một ngữ cảnh [1]. Nhóm vai trò không tách biệt hoàn toàn mà được đặc trưng hóa bởi các thuộc tính nổi bật có tính thường xuyên trong ngữ cảnh xã hội. Như chúng ta đã biết, mạng xã hội không thừa kế mối quan hệ trong xã hội thực của các thành viên, tuy nhiên, thông tin về hành vi và nội dung thông điệp trao đổi trong mạng xã hội cho phép phát hiện các mối quan hệ giữa các thành viên trong mạng bao gồm mối quan hệ trong xã hội thực lẫn mối quan hệ nảy sinh trong ngữ cảnh mạng xã hội. Một vai trò xã hội là tập hợp những đặc tính mô tả cách hành xử của mỗi cá nhân và mối liên hệ giữa họ trong một ngữ cảnh nhất định. Trong nghiên cứu [21], một vai trò xã hội được định nghĩa thông qua một tập các độ đo thích hợp đặc trưng cho những nhóm người trong một ngữ cảnh. Phát hiện vai trò trong mạng xã hội chính là nội dung nghiên cứu, làm rõ mô hình toán học cho sự tương tác, vai trò giữa con người, các tổ chức và các nhóm với nhau trong việc phân tích mạng xã hội. Rất nhiều những nghiên cứu về việc xác định vai trò cụ thể trong ngữ cảnh như trong các cuộc thảo luận trực tuyến, Wikipedia và phương tiện truyền thông. Nhưng phần lớn các nghiên cứu chỉ tập trung vào vịêc phân tích và định nghĩa một vai trò đặc trưng với mạng đó chứ không đưa ra một kiến trúc để truy tìm các vai trò trong mạng. Đầu tiên, họ phân tích mạng và mục tiêu của việc nghiên cứu này là tìm ra những vai trò có thể có. Sau đó họ đặc trưng hóa chúng cùng với những đặc tính được quan sát và cố gắng thu thập những mẫu đáp ứng các tiêu chuẩn đó [13, 24]. Những hướng tiếp cận này phụ thuộc vào mạng đang nghiên cứu và chỉ phục vụ cho vịêc tìm kiếm một vai trò cụ thể. Ví dụ, nghiên cứu phát hiện vai trò trên mạng Twitter chủ yếu tập trung vào việc xác định một vai trò cụ thể nào đó như nhà cải cách, người nổi tiếng hay những nhà sản xuất giỏi [4]. Những nghiên cứu trên 18 các mạng khác như Wikipedia hay Youtube đưa ra những quy lụât phân loại người dùng vào các nhóm hoặc phân cụm người dùng và sau đó gán vai trò cho các cụm [14, 18, 22]. Trong luận văn này, chúng tôi sẽ trình bày một mô tả kiến trúc của một máy tìm kiếm để xác định một vai trò trong thời gian thực dựa trên hướng tiếp cận của Trabado và cộng sự [21]. Hướng tiếp cận của [21] được tiến hành dựa trên bước tiền xử lý biểu diễn mỗi người trong mạng bằng một vec-tơ đặc trưng mô tả hành vi và mối quan hệ của người đó với những người khác trong cộng đồng. Sau đó, thực hiện phương pháp phân cụm trên tập các vec-tơ đặc trưng để gom nhóm những người có đặc trưng tương đồng lại với nhau. Nền tảng tiền xử lý phân cụm người trong mạng hoàn toàn độc lập với đặc trưng vai trò mà người sử dụng sẽ tìm kiếm sau đó. Trong thực tế, người dùng đặt ra các truy vấn của máy tìm kiếm vai trò như một tập các độ đo phù hợp. Trong luận văn, độ đo phù hợp là một tập các đặc trưng để phân biệt mỗi một người trong mạng. Hệ thống phát hiện các phân cụm thích hợp dựa trên các đặc trưng hóa của vai trò. Quá trình phân cụm hoàn toàn độc lập với vai trò và không có ảnh hưởng lớn tới việc gán vai trò cho nhóm. Tóm tắt chƣơng 1 Chương một đã trình bày tổng quan về mạng xã hội, sự phát triển của mạng xã hội, mạng xã hội trực tuyến Twitter và bài toán phát hiện vai trò trong mạng xã hội. Đồng thời, chương này cũng nêu một số phương pháp và các cách tiếp cận xác định vai trò trong mạng xã hội Chương hai của luận văn sẽ trình bày chi tiết về một trong những cách được sử dụng để tìm kiếm, phát hiện vai trò trong mạng xã hội nói chung và trong mạng xã hội Twitter nói riêng. Đồng thời trong chương này, cũng trình bày về một thuật toán phân cụm cải tiến. 19 Chƣơng 2. Các phƣơng pháp phát hiện vai trò trong mạng xã hội và một số thuật toán phân cụm 2.1. Các phƣơng pháp phát hiện vai trò trong mạng xã hội Việc nghiên cứu phát hiện vai trò trong môi trường trực tuyến bắt đầu trước sự bùng nổ của các trang mạng xã hội trực tuyến. Năm 2005, Nolker và cộng sự đã nghiên cứu những cuộc thảo luận lớn và phát hiện hai vai trò quan trọng tới sự thành công của cộng đồng: người đứng đầu, người cung cấp kiến thức và duy trì sự gắn kết của nhóm, và người thúc đẩy – người giữ cho cuộc hội thảo tiếp diễn [17]. Họ được xác định dựa trên hành vi, các cuộc trao đổi và mối liên hệ với các thành viên. Một số nghiên cứu khác tập trung vào một số mạng cụ thể như Usenet hay Yahoo! Group. Trong Usenet, một số vai trò đã được nhận dạng: chuyên gia, người trả lời, người nói chuyện, người hâm mộ, nghệ sĩ hội thảo, người pha trò và người lừa dối. Những vai trò này được xác định thông qua những tương tác với các thành viên khác, hành vi và mẫu cấu trúc của họ [8]. Vai trò của người trả lời trong các nhóm hội thảo trực tuyến – người cung cấp những thông tin trợ giúp cho những câu hỏi của các thành viên khác trong nhóm thì rất dễ nhận biết trong những mạng kiểu này [24]. Việc xác định những người gắn bó lâu dài là vịêc rất quan trọng vì họ chính là những thành viên duy trì các cuộc thảo luận. Vai trò đóng góp cũng đang được nghiên cứu trong nhóm Yahoo! Group [2]. Rất nhiều đề nghị được đưa ra trong Twitter và vịêc lấy dữ liệu từ nó trở nên dễ dàng. Chúng ta có thể phân biệt một số vai trò tương tác trên Twitter như nguồn thông tin chính truyền bá thông tin trên mạng; những người nổi tiếng – được theo dõi bởi rất nhiều người; người dẫn dắt ý tưởng – người phổ biến các ý kiến của mình và có ảnh hưởng lớn tới những người khác trong mạng. Nội dung trên Twitter được tạo ra bởi hàng trăm triệu người. Chúng tacó thể phân bịêt những tác giả hấp dẫn nhất cho từng từng chủ đề như một vai trò khác nhau. Nhưng với sự mở rộng mối liên hệ và sự phát triển rộng rãi của các mạng xã hội tạo ra một vai trò mới: spammer. Những spammer này sử dụng mạng xã hội để phát tán phần mềm độc hại hoặc các tin nhắc rác thương mại [26] Gleave và cộng sự đề xuất một phương pháp định tính nhằm xác định những tập vai trò tiềm năng ban đầu và những thước đo để phân tích chúng [22]. Phương pháp 20
- Xem thêm -