Bài giảng Phát hiện vai trò và dự báo bùng nổ sự kiện trên mạng xã hội - Hà Quang Thụy

Phát hiện vai trò và dự báo bùng nổ sự kiện trên mạng xã hội1KTLabHà Quang ThụyPhòng Thí nghiệm Công nghệ Tri thức - KTLabTrường ĐHCN, Đại học Quốc gia Hà Nội,Hà Nội, 29-9-2012Nội dung08 September 20212Giới thiệu chungKhai phá dữ liệu mạng xã hộiPhát hiện vai trò và dự báo bùng nổ sự kiện trên xã hộiMột mô hệ thống hình phát hiện vai trò và dự báo bùng nổ sự kiện trên xã hộiMột vài bàn luậnĐặt vấn đề08 September 20213Dự báo bùng nổ sự kiệnKTLab: Nâng cao chất lượng phát hiện sự kiệnHợp tác quốc tếNII (Nhật Bản): Event Sequence AnalysisLARC (Singapore): Event BurstingCatholic University of Leuven (Katholieke Universiteit Leuven, Bỉ): Dự án hợp tác quốc tế “Improving Business Process and Complex Event Sequence Analytics using Process Mining Techniques”Hợp tác trong nước: Bộ Công anPhát hiện vai trò với bùng nổ sự kiệnKTLab: Phát hiện vai trò, xếp hạng trong mạng xã hội, khai phá quan điểm cộng đồngVai trò lớn/hạng cao, cộng đồng  sự kiện / bùng nổ sự kiệnDự báo bùng nổ sự kiện liên quan tới nút có vai trò lớnI. Giới thiệu chung08 September 20214Khái niệm mạng xã hộiJohn Arundel Barnes, 1954: mạng xã hội là đối tượng nghiên cứu [Barnes54].Cấu trúc xã hội: tập các cá nhân/tổ chức + tập các quan hệ xã hội giữa các cá nhân/tổ chức [EK10]. Biểu diễn đồ thị.Phương tiện truyền thông XH (social media): phương tiện phổ biến mối quan hệ XH tới cộng đồng. Trao đổi nội dung [Lesk11]Phương tiện truyền thông XH là nền tảng để người dùng tạo và trao đổi nội dung với cộng đồng [YK12]"một nhóm các ứng dụng dựa trên Internet được xây dựng trên nền tảng tư tưởng và công nghệ của Web 2.0, cho phép tạo và trao đổi nội dung do người dùng tạo ra“ [KH10]Phân loại mạng xã hộiHai chiều đặc trưng: hiện diện xã hội/phong phú (social presence/media richness) và hiện diện xã hội/phong phú (self-presentation/self-disclosure).[Barnes54] Barnes, J. (1954). Class and Committees in a Norwegian Island Parish, Human Relations, 7, 39-58.[EK10] David Easley and Jon Kleinberg (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press, 2010.[KH10] Andreas M Kaplan and Michael Haenlein (2010). Users of the world, unite! The challenges and opportunities of Social Media, Business horizons (2010), 53:59-68.[YK12] Sheng Yu, Subhash Kak (2012). A Survey of Prediction Using Social Media CoRR abs/1203.1647: (2012)I. Một cách phân loại mạng xã hội08 September 20215[KH10] Andreas M Kaplan and Michael Haenlein (2010). Users of the world, unite! The challenges and opportunities of Social Media, Business horizons (2010), 53:59-68.Twitter ?I. Sự phát triển của mạng xã hội08 September 20216[Ben12], Shea Bennet (2012). Twitter On Track For 500 Million Total Users By March, 250 Million Active Users By End Of 2012, Tác động của mạng xã hội08 September 20217Tác động xã hộiGóp phần tăng cường nguồn vốn xã hội (social capital) cho quốc gia [ESL07], [ZJV12]Đôi lúc cản trở phát triển xã hộiFacebook với phong trào “Mùa xuân Ả rập”Facebook góp phần quan trọng [AMCJ12], [Iskan11], [MS11]: hoạt động liên quan đến phong trào chiếm trọng số rất lớn (3 dòng cuối)[AMCJ12] Ban Al-Ani, Gloria Mark, Justin Chung, Jennifer Jones (2012). The Egyptian Blogosphere: A Counter-Narrative of the Revolution, Proceedings of the ACM 2012 conference on Computer Supported Cooperative Work: 17-26.[Iskan11] Elizabeth Iskander (2011). Connecting the National and the Virtual: Can Facebook Activism Remain Relevant After Egypt’s January 25 Uprising?, International Journal of Communication 5 (2011): 1225–1237.[MS11] Racha Mourtada and Fadi Salem (2011). Civil Movements: The Impact of Facebook and Twitter, Arab Social Media Report, 1 (2): 1-30.I. Tác động xã hội của mạng xã hội08 September 20218Facebook với cuộc bạo loạn tại Anh năm 2011Liên quan giữa mức độ bạo lực với sự kiểm duyệt Facebook [AT12]Giải pháp tối ưu khuyêch tán quan điểm lành mạnh: Tham gia cởi mở cung cấp thông tin đúng và hoàn toàn không áp đặt.Mạng xã hội với chống quyền lợi Mỹ 9/2012Xuất phát từ video về Thánh MohamedĐại sứ Mỹ tại Libi bị giết. Hai phía sử dụng mạng xã hộiTwitter với sự kiện thảm họa kép “Động đất – Sóng thần” ở Nhật Bản 3/2011“Phóng viên nhân dân” (Real time citizen journalist [ZJV12]Tính thời gian thực của Twitter; Mô hình xác suất dự báo và lan truyền thông tin động đất [SOM10] nhanh hơn C/quan KTTV-NB.Tư vấn sau thảm họa [CD11, DVC11][AT12] Casilli, Antonio A. and Paola Tubaro (2012). Social media censorship in times of political unrest: A social simulation experiment on the UK riots, Bulletin of Sociological Methodology, 115 (1): 5-20.[CD11] Nigel Collier, Son Doan (2011). Syndromic Classification of Twitter Messages, eHealth 2011: 186-195[SOM10] Takeshi Sakaki, Makoto Okazaki, Yutaka Matsuo (2010). Earthquake shakes Twitter users: real-time event detection by social sensors, WWW 2010: 851-860.[STM11] Takeshi Sakaki, Fujio Toriumi, Yutaka Matsuo (2011). Tweet trend analysis in an emergency situation, SWID '11: 3.[ZJV12] Homero Gil de Zúnĩga, Nakwon Jung, Sebastián Valenzuela (2012). Social Media Use for News and Individuals’ Social Capital, Civic Engagement and Political Participation, Journal of Computer-Mediated Communication 17 (2012) 319–336I. Tác động khoa học08 September 20219Ngành xã hội học [WGG12]5 nhóm chủ đề dựa trên Facebook: Phân tích mô tả người sử dụng, Động lực sử dụng Facebook, Trình bày danh tính, Vai trò của Facebook trong tương tác xã hội, Tính riêng tư và việc tiết lộ thông tin.Phát sinh hướng nghiên cứu mới: "Netnography" = “Inter[net]” and “eth[nography]”; "Child-led Research"Khoa học máy tính: khai phá dữ liệu mạng xã hộiLà nguồn tài nguyên thông tin phong phú [LVGE12]Miền ứng dụng rộng lớn [EK10], [HSYY10], [Lesk11]Khai phá dữ liệu cấu trúc + Khai phá dữ liệu nội dung[WGG12] Robert E. Wilson, Samuel D. Gosling, and Lindsay T. Graham (2012). A Review of Facebook Research in the Social Sciences, Perspectives on Psychological Science 7(3) 203– 220.[LVGE12] Cliff Lampe, Jessica Vitak, Rebecca Gray, Nicole B. Ellison (2012). Perceptions of facebook's value as an information source, CHI 2012: 3195-3204[EK10] David Easley and Jon Kleinberg (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press, 2010[HSYY10] Jiawei Han, Yizhou Sun, Xifeng Yan, Philip S. Yu (2010). Mining Knowledge from Databases: An Information Network Analysis Approach, ACM SIGMOD Conference Tutorial, 2010.[Lesk11] Jure Leskovec (2011). Social Media Analytics, Tutorial at the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Part 1: Information flow, Part2: Rich Interactions), 2011.II. Khai phá dữ liệu mạng xã hội08 September 202110Khai phá nội dung mạng xã hội [HSYY10, Lesk11]quản lý danh tiếng (reputation management)tiếp thị phương tiện truyền thông xã hội (Social media marketing)phản ứng công dân (citizen response)phân tích hành vi con người (Human behavior analysic)phóng viên công dân thời gian thực (Real time citizen journalist)...Khai phá cấu trúc mạng xã hộimẫu và tính động về cấu trúc của mạng xã hộithế giới nhỏ (small world)liên kết mạnh – yếu (strong – weak tie)phân bố luật lũy thừa (power law distribution)cấu trúc cộng đồng (community)Dự báo liên kết L. Liu và T. Zhou, 2010 [LZ10]lý thuyết cân bằng (balance theory) và lý thuyết trạng thái (status theory) [EK10][LZ10] L. Lu and T. Zhou (2010). Link prediction in complex networks: A survey, Physica A, 390:1150–1170, 2010II. Một số tổ chức nghiên cứu KPDL mạng xã hội08 September 202111Viện Tiêu chuẩn và công nghệ quốc gia Mỹ (NIST)Nhánh hội nghị TREC: Blogsphore 2010, Microblogs 2011, 2012.Blogtrack 2010 [MSOS10]: Kho ngữ liệu Blogs06 và Blogs08Ba bài toán Tìm quan điểm (Opinion-Finding), Lọc tìm thú vị ((Blog Distillation), và Phát hiện tin nóng (Top news).45 nhóm nghiên cứu tham giaTìm quan điểm: dựa theo phân lớp, dựa theo từ vựngTiếp cận lọc tìm thú vị: lựa chọn tài nguyên, lựa chọn chuyên giaPhát hiện tin nóng: bỏ phiếu, xệp hạngMicroblog Track 2011, 2012NIST tạo ra 60 chủ đề,giải quyết trong thời gian thực,tìm kiếm và xếp hạng tweest2011: công bố của 34 nhóm trên thế giới C. McCreadie và cộng sự, 2012 [CSMOC12][MSOS10] Craig Macdonald, Rodrygo L. T. Santos, Iadh Ounis, Ian Soboroff (2010). Blog track research at TREC, SIGIR Forum 44(1): 58-75 (2010)[CSMOC12] Richard M. C. McCreadie, Ian Soboroff, Jimmy Lin, Craig Macdonald, Iadh Ounis, Dean McCullough (2012). On building a reusable Twitter corpus, SIGIR 2012: 1113-1114II. Viện Tin học quốc gia Nhật Bản08 September 202112Nội dung hợp tác nhóm GS Collier và KTLabHiểu được yêu cầu người dùng khi gặp tình huống khẩn cấpTheo dõi sự biến đổi khí hậuPhân tích danh tiếng của các sản phẩmKhám phá, theo dõi chủ đề và phân tích quan điểm của người sử dụng liên quan tới thảm họaMột số nội dung cụ thểPhân lớp hội chứng từ dữ liệu Twitter [CD11].Phân tích thông điệp Twitter về động đất [DVC11]Dự báo thay đổi phân cực chứng khoán bốn cổ phiếu Apple (AAPL), Google (GOOG), Microsoft (MSFT) và Amazon (AMZN). Seminar tiếp theo.[CD11] Nigel Collier, Son Doan (2011). Syndromic Classification of Twitter Messages, eHealth 2011: 186-195[DVC11] Son Doan, Bao-Khanh Ho Vo, Nigel Collier (2011). An Analysis of Twitter Messages in the 2011 Tohoku Earthquake, eHealth 2011: 58-66.[TSQN12] Tien Thanh Vu, Shu Chang, Quang Thuy Ha, Nigel Collier (2012). An Experiment in Integrating Sentiment Features for Tech Stock Prediction in Twitter, Colling 2012 (being submitted).Viện Tin học quốc gia Nhật Bản08 September 202113[TSQN12] Tien Thanh Vu, Shu Chang, Quang Thuy Ha, Nigel Collier (2012). An Experiment in Integrating Sentiment Features for Tech Stock Prediction in Twitter, Colling 2012 (being submitted).II. LARC, SMU08 September 202114Quá trình vòng kín 4 phaExperiment-Driven Closed-Loop AnalyticsQuan sát: quan sát tương tác và mối quan hệ người dùng mạng thời gian thực và thu thập các dấu vết kỹ thuật số.Phân tích và Dự báo: tiếp nhận, phân tích dấu vết kỹ thuật số phát hiện các mẫu để dự báo hành vi người dùng và xu hướng mạng.Thực nghiệm: kiểm tra cách cá nhân/nhóm phù hợp với sự thay đổi về nội dung, cung cấp dịch vụ, kinh nghiệm tương tác, giá và ưu đãiHành động con người: người dùng tạo ra trả lời từ thực nghiệm thông qua các loại thông tin phản hồi  dữ liệu cho pha Quan sát.Khái niệm phân tích cuộc sốngphân tích hành vi và mạng xã hội và thực nghiệm hành viphát hiện và thu hoạch các luật tiến hóa đối với các mạng08 September 202115Wayne Xin Zhao và cộng sự, 2011 [ZJHS11]Topic discovery, Topical PageRank for Keyword Ranking, Probabilistic Models for Topical Keyphrase RankingQiming Diao và cộng sự, 2012 [DJZL12][DJZL12] Qiming Diao, Jing Jiang, Feida Zhu and Ee-Peng Lim (2012). Finding bursty topics from microblogs, ACL'12: 536-544, 2012[ZJHS11] Wayne Xin Zhao, Jing Jiang, Jing He, Yang Song, Palakorn Achanauparp, Ee-Peng Lim and Xiaoming Li (2011) Topical keyphrase extraction from Twitter, ACL-HLT'11: 379-388, 2011II. LARC, SMU: Bùng nổ sự kiện08 September 202116Wayne Xin Zhao và cộng sự, 2012 [ZSJSL12]Xung quanh cùng thời gian và cùng một chủ đềCùng một người và cùng chủ đề[ZSJSL12] Wayne Xin Zhao, Baihan Shu, Jing Jiang, Yang Song, Hongfei Yan and Xiaoming Li (2012). Identifying Event-related Bursts via Social Media Activities, EMNLP-CoNLL'12:1466-1477, 2012.II. LARC, SMU: Bùng nổ sự kiệnIII. Phát hiện vai trò08 September 202117Quan hệ xã hội thựcĐịnh nghĩa: tập nút và tập quan hệKhông như CSDL quản lý quan hệ xã hội: “quen biết”Cần phát hiện quan hệ xã hội trong xã hội thựcMạng thành viên câu lạc bộ Karate có hai cộng đồng: huấn luyện viên và chủ CLBMạng email: phân cấp vai tròQuan hệ mạng thông tin công trình khoa họcMột số giải phápMô hình đồ thị nhân tử xác suất theo thời gian [WHJTZ10]Xếp hạng đối tượng[WHJTZ1] 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-212Hệ thống tìm kiếm vai trò [TS12]08 September 202118Mô hình chung phát hiện vai tròThực thể và quan hệ:3 kiểu thực thể/nút: Người dùng, tài liệu, thẻ (tag): Một từ bắt đầu với dấu “#” 5 kiểu cung liên kết: Person-publishes, Person-receives, Depicts, Knows, References[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Hệ thống tìm kiếm vai trò [TS12]08 September 20211914 đặc trưng phản ánh vai trò (M1-M14)M1: Số lượng người mà p biếtM2: Số lượng người biết p “số fan hâm mộ”M3: Số lượng mối quan hệ đối ứng của pM4: Hệ số phân cụm mối quan hệ từ các độ đo ràng buộc với bạn bè của pM5: Độ sâu truyền thông trung bình của người p (chi tiết sau)M6: Độ sâu truyền thông tối đa của người p (tương tự M5)M7: Số lượng tin nhắn mà p nhận đượcM8: Số tài liệu mô tả pM9: Thời gian trung bình các hành động ảnh hưởng được p thực hiệnM10: Vị trí trung bình mà người p xuất hiện trong dòng truyền thôngM11: Số lượng các ấn phẩm của pM12: Ngày p tham gia vào mạngM13: Trung bình số lượng từ trong các tài liệu của p XBM14: Chỉ số đăng ký của p: 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[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Hệ thống tìm kiếm vai trò [TS12]08 September 202120Tính độ sâu TT 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 3[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Vai trò quan trọng [TS12]08 September 202121 Người nổi tiếng (Celebrities)Người của công chúng như Lady Gaga, Gisele Bundchen: thu hút fan, có danh sách ?Liên kết nhiều nhưng có thể ảnh hưởng ít M2 và M8Người lãnh đạo (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 quảng bá (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ọM9, M10Người nhanh nhậy (Early adopters)Tích cực phân phối nội dungM9 và M10[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Xử lý dữ liệu [TS12]08 September 202122Phân cụm người dùngThuật toán k-meanHai nội dung: chuẩn hóa dữ liệu, gán vai trò cho mỗi cụmChiến lược chuẩn hóaChuẩn hóa tối đa/tối thiếu về [0,1]Chuẩn hóa logarithmChuẩn hóa hạngGán vai tròXem xét phân bổ dữ liệu theo 14 đặc trưng M1-M14[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Hệ thống tìm kiếm vai trò [TS12]08 September 202123Vai trò với các đặc trưng[TS12] Vanesa Junquero-Trabado, David Dominguez-Sal (2012). Building a role search engine for social media. WWW (Companion Volume) 2012: 1051-1060Dự báo bùng nổ sự kiện08 September 202124Phân hướng xu hướng Tweet[STM11], Takeshi Sakaki và cộng sựphân tích xu hướng Tweet xung quanh sự kiện thảm họa kép "động đật – sóng thần“Phân tích yếu tố tạo bùng nổ sự kiện[ZJHS11, ZSJSL12] và [DJZL12] Phân tích các yếu tố góp phần tạo ra sự bùng nổ sự kiệnDự báo bùng nổ sự kiện.Phân tích chủ đề ẩnĐược sử dụng trong [ZJHS11, ZSJSL12]Dữ liệu miền ứng dụng lớn, thu thập được và theo phong cách riêng phù hợp với mạng xã hôi.[STM11] Takeshi Sakaki, Fujio Toriumi, Yutaka Matsuo (2011). Tweet trend analysis in an emergency situation, SWID '11: 3[ZJHS11] Wayne Xin Zhao, Jing Jiang, Jing He, Yang Song, Palakorn Achanauparp, Ee-Peng Lim and Xiaoming Li (2011) Topical keyphrase extraction from Twitter, ACL-HLT'11: 379-388, 2011[ZJV12] Homero Gil de Zúnĩga, Nakwon Jung, Sebastián Valenzuela (2012). Social Media Use for News and Individuals’ Social Capital, Civic Engagement and Political Participation, Journal of Computer-Mediated Communication 17 (2012) 319–336IV. Hệ thống phần mềm08 September 202125Nội dungPhát hiện vai trò trong mạng xã hội,Dự báo sự bùng nổ sự kiện trong mạng xã hội theo hai tình huốngBùng nổ sự kiện toàn cụcBùng nổ sự kiện cục bộ: một bộ phận mạng xã hội, một số thành viên có vai trò đặc biệt Hỗ trợ nghiệp vụHai phaHọc mô hìnhSử dụng mô hìnhKết hợp các mạng xã hộiCho thông tin hỗ trọ phát hiện bùng nổ sự kiện từ các mạng khác nhauIV. Học mô hình08 September 202126Thu thập dữ liệu học từ mạng xã hội,Tiền xử lý dữ liệu,Xây dựng tập đặc trưng cho mô hình học,Thực hiện thuật toán học mô hình,Đánh giá mô hình kết quả,Tiếp nhận mô hình có chất lượng[Barnes54] BarnesSử dụng mô hình08 September 202127Thu thập dữ liệu hiện thời trên mạng xã hội,Tiền xử lý dữ liệu, trích chọn đặc trưng,Thực hiện mô hình bài toán Trực quan hóa kết quả mô hình để hỗ trợ người sử dụng ra quyết định tương ứng.[Barnes54] BarnesThu thập dữ liệu từ Facebook08 September 202128Các hình thức thu thập dữ liệuRobert E. Wilson và công sự [WGG12] Chiêu mộ người tham gia theo ngữ cảnh ngoại tuyến,Chiêu mộ người tham gia theo ngữ cảnh trực tuyến,thu thập tự động (crawling) dữ liệu.Thu thập tự động, trực tuyếnThu thập thông tin thành viên và đồ thị các mối liên kết bạn bèĐăng nhập vào tài khoản FacebookVào địa chỉ https://developers.facebook.com/tools/explorer/ để lấy Access token tương ứng[Barnes54] BarnesThu thập dữ liệu từ Facebook08 September 202129Một số phương pháp chính Friends: Danh sách các liên kết bạn bèhttps://graph.facebook.com/me/friends?access_token= News feed: Thông tin cập nhập các hoạt động của bạn bè, Group, Page đã đăng ký, https://graph.facebook.com/me/home?access_token= Thu thập từ các pageDanh sách địa chỉ của page [Barnes54] BarnesThu thập dữ liệu từ Twitter08 September 202130Một số phương pháp chính Một số nhận xét[Barnes54] BarnesMột số bàn luận08 September 202131Đề nghị một dự án Nội dung về hệ thống liên quanThực hiện tháng 10/2012-12/2013Một số công trình sinh viên NCKH tham gia trực tiếp hệ thốngKết hợp với các dự án khácTRÂN TRỌNG CÁM ƠN32KT-SISLAB