Bài giảng Khai phá vai trò trong mạng xã hội trực tuyến Twitter

Khai phá vai trò trong mạng xã hội trực tuyến Twitter1Nội dungGiớ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ộiMột số nghiên cứu liên quanMô hình tìm kiếm vai trò2Giới thiệu mạng xã hội3Thuật ngữ “mạng xã hội” lần đầu tiên được Barnes [Barnes54] đưa ra vào năm 1954.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 1 hoặc nhiều cung[BKMNT08].Mỗi nút (tác nhân) biểu diễn cho 1 đối tượng xã hội: một người, một tài liệu, một tổ chức, 1 quốc giaLiên kết giữa các nút có thể là quan hệ họ hàng,bạn bè, đồng nghiệphay các trao đổi tài chính, giao dịchGiới thiệu mạng xã hội4Mạng xã hội được biểu diễn bởi 2 cấu trúc phổ biến : đồ thị và ma trận kề. Để tính toán và phân tích các liên kết trong mạng, thường ưu tiên áp dụng lý thuyết đồ thị do đồ thị là 1 trong những công cụ hữu hiệu để thể hiện các thông tin xã hội.Các đỉnh được dùng để biểu diễn các nútCác cạnh dùng để biểu diễn liên kết giữa các nút, các cạnh có thể có hướng hoặc vô hướng và có thể được đánh trọng số.Giới thiệu mạng xã hội Twitter5Được thành lập từ năm 2006Là một trang micro-blog được phát triển bởi Twitter Inc cung cấp 1 dịch vụ mạng miễn phí cho phép người dùng sử dụng gửi và nhận các tin nhắn (Tweet) Là mạng xã hội nhắn tin: những mẩu Tweet 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.Giới thiệu mạng xã hội Twitter6Twitter là một công cụ xã hội nhờ tính phổ biến và khả năng lan truyền: Tổng thống Mỹ Obama đã sử dụng rất tích cực và hiệu quả công cụ này khi chạy đua vào nhà Trắng, được các tạp chí, các ngôi sao dùng để kết nối với khán giả và người hâm mộCó thể biểu diễn dưới dạng mô hình đồ thịCung cấp 1 API giúp người sử dụng có thể lấy được các thông tin về các người dùng trong mạng xã hội như tên truy cập, ID, số lượng bạn bè, số lượng tweet mỗi ngàyGiới thiệu bài toán khai phá vai trò 7Mộ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 địnhMạng xã hội không kế thừa những 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 => Bài toán khai phá vai trò ra đời.Một số nghiên cứu về khai phá vai tròNghiên cứu phát hiện vai trò trong xã hội 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ếnNolker và cộng sự [NZ05] đã nghiên cứu 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.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ộ, chuyên gia 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ọ [GD04]8Một số nghiên cứu về khai phá vai tròGleave và cộng sự [WCKLD11] đề 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 để xác định các vai trò trong Wikipedia .Chi Wang và cộng sự, 2010 [WHJTZ10] đề xuất mô hình đồ thị nhân tử xác suất phụ thuộc thời gian (Time-constrained probabilistic factor graph model: TPFG) để phát hiện quan hệ người hướng dẫn – người được hướng dẫn trong mạng thông tin được hình thành từ Cơ sở dữ liệu DBLP9Mô hình tìm kiếm vai tròTrabado và cộng sự [TS12] đề xuất một kiến trúc cho hệ thống tìm kiếm vai trò từ những người dùng phương tiện xã hội. Các tác giả định nghĩa 14 đặc trưng cần thiết liên quan tới các vai trò và thực nghiệm trên tập dữ liệu Twitter tìm kiếm 4 vai trò là người nổi tiếng (Celebrity), người lãnh đạo quan điểm (Information propagators), người phát kiến (Promoters) và người vận động quảng bá (Early adopters). Việc xác định vai trò trong mô hình này không phụ thuộc vào mạng một xã hội hay một vai trò cụ thể nào10Mô hình tìm kiếm vai tròĐược chia làm 2 pha:Pha ngoại tuyến: mô hình hóa dữ liệu, đặc trưng hóa cá nhân, chuẩn hóa dữ liệu và phân cụm cá nhân vào các nhóm (sử dụng phương pháp phân cụm K- mean)Pha trực tuyến, người dùng truy vấn hệ thống và máy tìm kiếm sẽ tiến hành gán vai trò (bằng việc lựa chọn seed và quá trình mở rộng tập seed ).11Mô hình đề xuất (t)Pha ngoại tuyến:12Mô hình đề xuất (t) Pha trực tuyến.13Pha ngoại tuyến Mô hình hóa dữ liệu: xây dựng đồ thị thực thể quan hệ 3 kiểu thực thể/nút: Con người, tài liệu (tweet) và các tag: một từ được bắt đầu với dấu “#” 5 kiểu cung liên kết:person-publishes, person -receives,depicts,Knows,References14Pha ngoại tuyến(t) Đặc trưng hóa dữ liệu: Định nghĩa 14 đặc trưng cần thiết phản ánh các vai tròM1: Số lượng người p biết.M2: Số lượng người biết p.M3: Mối quan hệ tương tác của p.M4: Hệ số phân cụm của liên hệ đã biết, nó cho biết mức độ gắn kết những người bạn của p.M5: Độ sâu truyền thông trung bình của người p. Tính toán phạm vi tác động của người p trong mạng (chi tiết sau)M6: Độ sâu truyền thông tối đa của người p: độ sâu ảnh hưởng cao nhất của p đến trong mạng( Chi tiết sau)15Pha ngoại tuyến(t) Đặc trưng hóa dữ liệu:M7: Số lượng tin nhắn mà p nhận được.M8: Số tài liệu mô tả p.M9: Thời gian trung bình các hành động ảnh hưởng được p thực hiện. M10: Vị trí trung bình mà người p xuất hiện trong dòng truyền thông. M11: Số lượng các ấn phẩm của p.M12: Ngày p tham gia vào mạng.M13: Trung bình số lượng các từ trong các tài liệu được p xuất bản.M14: Tỷ lệ phần trăm từ mà tồn tại trong từ điển của tập tài liệu được p xuất bản. Từ điển được sử dụng là từ điển liên quan. Lấy số liệu như là một chỉ số về phong cách đăng ký của p.16Pha ngoại tuyến(t)Tính độ sâu truyền thông trung bình (M5) và cực đại (M6)B1: Xác định mọi tài liệu được p xuất bảnB2: Xác định được tất cả người bị ảnh hưởng từ tập tài liệu (bước 1): B nhận tài liệu của ATài liệu của B có tham khảo tài liệu của AB ghi tên vào một tài liệu nào đó của AB3: Tính khoảng cách từ p tới mỗi người từ bước 2: số lượng cung của con đường ngắn nhất giữa i và p theo mối quan hệ biết nhauB4: Độ sâu trung bình (M5)/ cực đại (M6) khoảng cách được xác định trong bước 317Pha ngoại tuyến(t)Vai trò quan trọng trong TwitterNgười nổi tiếng (Celebrities)Người của công chúng như Lady Gaga, Taylor Swift: thu hút fan lớnLiên kết nhiều nhưng có thể ảnh hưởng ít M2 và M8Người lãnh đạo quan điểm (Information propagators)Dư luận bắt nguồn từ người lãnh đạo tới phần còn lạiLượng thông tin qua lãnh đạo có thể không nhiềuM1, M5, M6, M11, M14Người phát kiến (Promoters)Người quảng bá bắt đầu một tư tưởng/phát kiến mới , những người khác liên hệ với họM5, M6, M9, M10Người vận động quảng bá (Early adopters)Tích cực phân phối nội dungM9 và M1018Pha ngoại tuyến (t)Chuẩn hóa dữ liệu: Sử dụng các phương phápChuẩn hóa tối đa/ tối thiểu [0,1]Chuẩn hóa logarithmChuẩn hóa xếp hạngĐiểm chuẩn19Pha trực tuyến Pha trực tuyến được chia thành 2 bước: Bước đầu tiên, hệ thống lựa chọn các cụm tốt nhất thỏa mãn các đặc trưng với truy vấn mà người dùng đưa vào để tạo tập seed cho vai trò. Từ những cụm này, hệ thống tính toán được trọng tâm của vai trò và thu thập thêm nhiều cụm theo sau quá trình mở rộng tập seed. Quá trình này lặp lại cho tới khi nó hội tụ.Khi quá trình kết thúc, tất cả cá nhân trong tập seed ban đầu và mở rộng sẽ nằm trong một vai trò nào đó.20Phương pháp cấu hình và đánh giá21Tài liệu tham khảo[B86] B. J. Biddle. Recent developments in role theory.pages 67{92. Annual Review of Sociology, 1986[BKMNT08] L. Backstrom, R. Kumar, C. Marlow, J. Novak, and A. Tomkins. Preferential behavior in online groups. In WSDM, pages 117{128. ACM, 2008[CHBG10] M. Cha, H. Haddadi, F. Benevenuto, and P. Gummadi. Measuring user influence in twitter: The million follower fallacy. In ICWSM, 2010[GD04] S. A. Golder and J. Donath. Social roles in electronic communities. In AOIR, 2004.[JC10] Jiyang Chen, Community Mining-Discovery Communities in Social Network, Thesis, University of Alberta, 2010.[LTVK11] D. Laniado, R. Tasso, Y. Volkovich, and A. Kaltenbrunner. When the wikipedians talk:Network and tree structure of wikipedia discussion pages. In ICWSM. The AAAI Press, 2011[MA08] M. Maia, J. Almeida, and V. Almeida. Identifying user behavior in online social networks. In Proceedings of the 1st Workshop on Social Network Systems,SocialNets '08, pages 1{6, New York, NY, USA, 2008.ACM [NZ05] R. D. Nolker and L. Zhou. Social computing and weighting to identify member roles in online communities. In Web Intelligence, pages 87{93. IEEE Computer Society, 2005.[PC11] A. Pal and S. Counts. Identifying topical authorities in microblogs. In WSDM, pages 45{54, 2011.[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060.[WCKLD11] H. T. Welser, D. Cosley, G. Kossinets, A. Lin,F. Dokshin, G. Gay, and M. Smith. Finding social roles in wikipedia. In Proceedings of the 2011 iConference, iConference '11, pages 122{129, New York, NY, USA, 2011. ACM.[WGFS07] H. T. Welser, E. Gleave, D. Fisher, and M. Smith.Visualizing the signatures of social roles in online discussion groups. The Journal of Social Structure, 8(2), 2007. [WHJTZ10] Chi Wang, Jiawei Han, Yuntao Jia, Jie Tang, Duo Zhang, Yintao Yu, Jingyi Guo (2010). Mining advisor-advisee relationships from research publication networks, KDD 2010: 203-212.22Xin chân thành cảm ơn!23