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

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

1. Khai phá vai trò trong mạng xã hội trực tuyến Twitter 1
2. Nội dung  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  Một số nghiên cứu liên quan  Mô hình tìm kiếm vai trò 2
3. Giới thiệu mạng xã hội  Thuậ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 gia  Liên kết giữa các nút có thể là quan hệ họ hàng,bạn bè, đồng nghiệp hay các trao đổi tài chính, giao dịch 3
4. Giới thiệu mạng xã hội  Mạ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út  Cá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ố. 4
5. Giới thiệu mạng xã hội Twitter  Được thành lập từ năm 2006  Là 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. 5
6. Giới thiệu mạng xã hội Twitter  Twitter 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ày 6
7. Giới thiệu bài toán khai phá vai trò  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  Mạ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. 7
8. 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ến  Nolker 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] 8
9. Mộ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 DBLP 9
10. Mô 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ào 10
11. Mô 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 ). 11
12. Mô hình đề xuất (t)  Pha ngoại tuyến: 12
13. Mô hình đề xuất (t)  Pha trực tuyến. 13
14. Pha 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,References 14
15. Pha 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) 15
16. Pha 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. 16
17. Pha 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ản § B2: 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 A § Tài liệu của B có tham khảo tài liệu của A § B ghi tên vào một tài liệu nào đó của A § B3: 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 nhau § B4: Độ sâu trung bình (M5)/ cực đại (M6) khoảng cách được xác định trong bước 3 17
18. Pha ngoại tuyến(t)  Vai trò quan trọng trong Twitter  Người nổi tiếng (Celebrities)  Người của công chúng như Lady Gaga, Taylor Swift: thu hút fan lớn  Liên kết nhiều nhưng có thể ảnh hưởng ít  M2 và M8  Ngườ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ại  Lượng thông tin qua lãnh đạo có thể không nhiều  M1, M5, M6, M11, M14  Ngườ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, M10  Người vận động quảng bá (Early adopters)  Tích cực phân phối nội dung  M9 và M10 18
19. Pha ngoại tuyến (t)  Chuẩn hóa dữ liệu: Sử dụng các phương pháp  Chuẩn hóa tối đa/ tối thiểu [0,1]  Chuẩn hóa logarithm  Chuẩn hóa xếp hạng  Điểm chuẩn 19
20. Pha 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 đó. 20
21. Phương pháp cấu hình và đánh giá 21
22. Tà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. 22
23. Xin chân thành cảm ơn! 23