ĐẠ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 -