The importance of unexpectedness: Discovering buzzing stories in anomalous temporal graphs

Abstract

The real-time nature and massive volume of social-media data has converted news portals and micro-blogging platforms into social sensors, causing a flourishing of research on story or event detection in online user-generated content and social-media text streams. Existing approaches to story identification broadly fall into two categories. Approaches in the first category extract stories as cohesive substructures in a graph representing the strength of association between terms. The latter category includes approaches that analyze the temporal evolution of individual terms and identify stories by grouping terms with similar anomalous temporal behavior.

Both categories have their own limitations. Approaches in the first category are unable to distinguish ever-popular concepts from stories that buzz in a time interval of interest, i.e., attract an amount of attention that deviates significantly from the typical level observed. The second category ignores term co-associations and the wealth of information captured by them.

In this work we advance the literature on story identification by profitably combining the peculiarities of the two main state-of-the-art approaches. We propose a novel method that characterizes abnormal association between terms in a certain time window and leverages the graph structure induced by such anomalous associations so as to identify stories as subsets of terms that are cohesively associated in this graph. Experiments performed on two datasets extracted from a real-world web-search query log and a news corpus, respectively, attest the superiority of the proposed method over the two main existing story-identification approaches.

Keywords

Story identification event detection temporal graphs dense-subgraph extraction anomaly detection web-search logs

Get full access to this article

View all access options for this article.

References

C.C.

Aggarwal and

Subbian, Event detection in social streams, in: SDM, 2012, pp. 624–635.

Allan,

Lavrenko,

Malin and

Swan, Detections, bounds, and timelines: UMass and TDT-3, in: TDT Workshop, 2000, pp. 167–174.

Almerekhi,

Hasanain and

Elsayed, EveTAR: A new test collection for event detection in Arabic tweets, in: SIGIR, 2016, pp. 689–692.

Alsaedi,

Burnap and

Rana, Identifying disruptive events from social media to enhance situational awareness, in: ASONAM, 2015, pp. 934–941. doi:10.1145/2808797.2808879.

Alsaedi,

Burnap and

Rana, Can we predict a riot? Disruptive event detection using Twitter, TOIT 17(2) (2017), 18:1–18:26. doi:10.1145/2996183.

Althoff,

X.L.

Dong,

Murphy,

Alai,

Dang and

Zhang, TimeMachine: Timeline generation for knowledge-base entities, in: KDD, 2015, pp. 19–28. doi:10.1145/2783258.2783325.

Andersen and

Chellapilla, Finding dense subgraphs with size bounds, in: WAW, 2009, pp. 25–37.

Angel,

Sarkas,

Koudas and

Srivastava, Dense subgraph maintenance under streaming edge weight updates for real-time story identification, PVLDB 5(6) (2012), 574–585.

Asahiro,

Hassin and

Iwama, Complexity of finding dense subgraphs, Discr. Ap. Math. 121(1–3) (2002), 15–26. doi:10.1016/S0166-218X(01)00243-8.

10.

Atefeh and

Khreich, A survey of techniques for event detection in Twitter, Comput. Intell. 31(1) (2015), 132–164. doi:10.1111/coin.12017.

11.

O.D.

Balalau,

Bonchi,

T.-H.H.

Chan,

Gullo and

Sozio, Finding subgraphs with maximum total density and limited overlap, in: WSDM, 2015, pp. 379–388.

12.

Bansal,

Chiang,

Koudas and

F.W.

Tompa, Seeking stable clusters in the blogosphere, in: VLDB, 2007, pp. 806–817.

13.

Batagelj and

Zaveršnik, Fast algorithms for determining (generalized) core groups in social networks, ADAC 5(2) (2011), 129–145. doi:10.1007/s11634-010-0079-y.

14.

Becker,

Naaman and

Gravano, Beyond trending topics: Real-world event identification on Twitter, in: ICWSM, 2011.

15.

Berlingerio,

Bonchi,

Bringmann and

Gionis, Mining graph evolution rules, in: ECML-PKDD, 2009, pp. 115–130.

16.

Bogdanov,

Baumer,

Basu,

Bar-Noy and

A.K.

Singh, As strong as the weakest link: Mining diverse cliques in weighted graphs, in: ECML-PKDD, 2013, pp. 525–540.

17.

Bogdanov,

Mongiovì and

A.K.

Singh, Mining heavy subgraphs in time-evolving networks, in: IEEE ICDM, 2011, pp. 81–90.

18.

Bonchi,

Bordino,

Gullo and

Stilo, Identifying buzzing stories via anomalous temporal subgraph discovery, in: IEEE/WIC/ACM WI, 2016, pp. 161–168.

19.

Bordino,

Ferretti,

Firrincieli,

Gullo,

Paris,

Pascolutti and

Sabena, Advancing NLP via a distributed-messaging approach, in: IEEE Big Data, 2016, pp. 1561–1568.

20.

Bringmann,

Berlingerio,

Bonchi and

Gionis, Learning and predicting the evolution of social networks, IEEE Intelligent Systems 25(4) (2010), 26–35. doi:10.1109/MIS.2010.91.

21.

Castillo, Big Crisis Data: Social Media in Disasters and Time-Critical Situations, 1st edn, Cambridge University Press, New York, NY, USA, 2016.

22.

Chandola,

Mithal and

Kumar, Comparative evaluation of anomaly detection techniques for sequence data, in: IEEE ICDM, 2008, pp. 743–748.

23.

Charikar, Greedy approximation algorithms for finding dense components in a graph, in: APPROX, 2000, pp. 84–95.

24.

Chen and

D.B.

Neill, Non-parametric scan statistics for event detection and forecasting in heterogeneous social media graphs, in: KDD, 2014, pp. 1166–1175.

25.

Chen and

Saad, Dense subgraph extraction with application to community detection, TKDE 24(7) (2012), 1216–1230.

26.

Das Sarma,

Jain and

Yu, Dynamic relationship and event discovery, in: WSDM, 2011, pp. 207–216.

27.

Eppstein,

Löffler and

Strash, Listing all maximal cliques in sparse graphs in near-optimal time, in: ISAAC, 2010, pp. 403–414.

28.

Ferragina and

Scaiella, TAGME: on-the-fly annotation of short text fragments (by Wikipedia entities), in: CIKM, 2010, pp. 1625–1628.

29.

Fulda,

Brehmer and

Munzner, TimeLineCurator: Interactive authoring of visual timelines from unstructured text, IEEE TVCG 22(1) (2016), 300–309.

30.

Gao,

Song,

Liu,

Wang,

Wei,

Chen and

Cui, Tracking and connecting topics via incremental hierarchical Dirichlet processes, in: IEEE ICDM, 2011, pp. 1056–1061.

31.

A.V.

Goldberg, Finding a maximum density subgraph, Technical report, University of California at Berkeley, 1984.

32.

Günnemann and

Pfeffer, Finding non-redundant multi-word events on Twitter, in: ASONAM, 2015, pp. 520–525. doi:10.1145/2808797.2809390.

33.

Gupta,

Gao,

C.C.

Aggarwal and

Han, Outlier detection for temporal data: A survey, TKDE 26(9) (2014), 2250–2267.

34.

Healy,

Janssen,

E.E.

Milios and

Aiello, Characterization of graphs using degree cores, in: WAW, 2006, pp. 137–148.

35.

D.J.

Hill and

B.S.

Minsker, Anomaly detection in streaming environmental sensor data: A data-driven modeling approach, Environmental Modelling and Software 25(9) (2010), 1014–1022. doi:10.1016/j.envsoft.2009.08.010.

36.

Hoffart,

M.A.

Yosef,

Bordino,

Fürstenau,

Pinkal,

Spaniol,

Taneva,

Thater and

Weikum, Robust disambiguation of named entities in text, in: EMNLP, 2011, pp. 782–792.

37.

Hu,

Y.-R.

Lin and

Luo, Collective sensemaking via social sensors: Extracting, profiling, analyzing, and predicting real-world events, in: KDD, 2016, pp. 2127–2128. doi:10.1145/2939672.2945384.

38.

Imran,

Castillo,

Diaz and

Vieweg, Processing social media messages in mass emergency: A survey, ACM Comput. Surv. 47(4) (2015), 67:1–67:38. doi:10.1145/2771588.

39.

Imran,

Castillo,

Lucas,

Meier and

Vieweg, AIDR: Artificial intelligence for disaster response, in: WWW, 2014, pp. 159–162.

40.

S.T.

Jishan,

M.N.

Monsur and

H.A.

Rahman, Breaking news detection from the web documents through text mining and seasonality, Int. J. Knowl. Web Intell. 5(3) (2016), 190–207. doi:10.1504/IJKWI.2016.078714.

41.

Kalyanam,

Velupillai,

Conway and

G.R.G.

Lanckriet, From event detection to storytelling on microblogs, in: ASONAM, 2016, pp. 437–442.

42.

Karkali,

Rousseau,

Ntoulas, and

Vazirgiannis, Efficient Online Novelty Detection in News Streams, Springer, Berlin Heidelberg, 2013, pp. 57–71.

43.

Kawamae, Trend analysis model: Trend consists of temporal words, topics, and timestamps, in: WSDM, 2011, pp. 317–326.

44.

Khuller and

Saha, On finding dense subgraphs, in: ICALP, 2009, pp. 597–608.

45.

Kulkarni,

Singh,

Ramakrishnan and

Chakrabarti, Collective annotation of Wikipedia entities in web text, in: KDD, 2009, pp. 457–466. doi:10.1145/1557019.1557073.

46.

Kumar,

Liu,

Mehta and

L.V.

Subramaniam, Exploring a scalable solution to identifying events in noisy Twitter streams, in: ASONAM, 2015.

47.

Lee,

L.V.S.

Lakshmanan and

Milios, CAST: A context-aware story-teller for streaming social content, in: CIKM, 2014, pp. 789–798.

48.

Lee,

L.V.S.

Lakshmanan and

E.E.

Milios, Incremental cluster evolution tracking from highly dynamic network data, in: ICDE, 2014, pp. 3–14.

49.

V.E.

Lee,

Ruan,

Jin and

C.C.

Aggarwal, A survey of algorithms for dense subgraph discovery, in: Managing and Mining Graph Data, 2010.

50.

Leskovec,

Backstrom and

Kleinberg, Meme-tracking and the dynamics of the news cycle, in: KDD, 2009, pp. 497–506. doi:10.1145/1557019.1557077.

51.

Li,

Tai,

Zhang,

Yu and

Liu, Online bursty event detection from microblog, in: UCC, 2014, pp. 865–870.

52.

Li,

K.H.

Lei,

Khadiwala and

K.C.-C.

Chang, TEDAS: a Twitter-based event detection and analysis system, in: ICDE, 2012, pp. 1273–1276.

53.

Li,

Han,

Kim and

Gonzalez, ROAM: Rule- and motif-based anomaly detection in massive moving object data sets, in: SDM, 2007, pp. 273–284.

54.

Liang,

Caverlee and

Cao, A noise-filtering approach for spatio-temporal event detection in social media, in: ECIR, 2015, pp. 233–244.

55.

Liu,

He,

Gu,

Xiong and

Du, Detecting and tracking topics and events from web search logs, TOIS 30(4) (2012), 21:1–21:29. doi:10.1145/2382438.2382440.

56.

Loglisci,

Ceci and

Malerba, Relational mining for discovering changes in evolving networks, Neurocomputing 150 (2015) 265–288.

57.

Lu,

Yu,

Guo,

Zhang,

Chin,

Tian and

Cao, Trending words based event detection in Sina Weibo, in: BigDataScience, 2014, pp. 4:1–4:6.

58.

McCreadie,

Macdonald,

Ounis,

Osborne and

Petrovic, Scalable distributed event detection for Twitter, in: IEEE BigData, 2013, pp. 543–549.

59.

A.J.

McMinn,

Moshfeghi and

J.M.

Jose, Building a large-scale corpus for evaluating event detection on Twitter, in: CIKM, 2013, pp. 409–418.

60.

Mihalcea and

Csomai, Wikify!: Linking documents to encyclopedic knowledge, in: CIKM, 2007, pp. 233–242.

61.

Muthukrishnan,

Shah and

J.S.

Vitter, Mining deviants in time series data streams, in: SSDBM, 2004, pp. 41–50.

62.

Nomoto, Two-tier similarity model for story link detection, in: CIKM, 2010, pp. 789–798.

63.

Olteanu,

Vieweg and

Castillo, What to expect when the unexpected happens: Social media communications across crises, in: CSCW, 2015, pp. 994–1009.

64.

Osborne,

Petrovic,

McCreadie,

Macdonald and

Ounis, Bieber no more: First story detection using Twitter and Wikipedia, in: TAIA, 2012.

65.

Petrovic, Real-time event detection in massive streams, PhD thesis, University of Edinburgh, UK, 2013.

66.

Petrovic,

Osborne and

Lavrenko, Streaming first story detection with application to Twitter, in: NAACL HLT, 2010, pp. 181–189.

67.

Pink,

K.L.

Mackley,

Mitchell,

G.T.

Wilson and

Bhamra, Refiguring digital interventions for energy demand reduction: Designing for life in the digital-material home, Digital Materialities: Design and Anthropology (2016) 79.

68.

Pink,

Sumartojo,

Lupton and

C.H.

La Bond, Mundane data: The routines, contingencies and accomplishments of digital living, Big Data & Society 4(1) (2017).

69.

Pio,

P.F.

Lanotte,

Ceci and

Malerba, Mining temporal evolution of entities in a stream of textual documents, in: ISMIS, 2014, pp. 50–60.

70.

M.F.

Porter, An Algorithm for Suffix Stripping, Morgan Kaufmann Publishers Inc., 1997, pp. 313–316.

71.

Rayana and

Akoglu, Less is more: Building selective anomaly ensembles with application to event detection in temporal graphs, in: SDM, 2015, pp. 622–630.

72.

Rebbapragada,

Protopapas,

C.E.

Brodley and

C.R.

Alcock, Finding anomalous periodic time series, Machine Learning 74(3) (2009), 281–313. doi:10.1007/s10994-008-5093-3.

73.

Rozenshtein,

Anagnostopoulos,

Gionis and

Tatti Event detection in activity networks, in: KDD, 2014, pp. 1176–1185.

74.

Sarkas,

Angel,

Koudas and

Srivastava, Efficient identification of coupled entities in document collections, in: ICDE, 2010, pp. 769–772.

75.

S.B.

Seidman, Network structure and minimum degree, Social Networks 5(3) (1983), 269–287. doi:10.1016/0378-8733(83)90028-X.

76.

Shah,

W.B.

Croft and

Jensen, Representing documents with named entities for story link detection (SLD), in: CIKM, 2006, pp. 868–869.

77.

Shen,

Wang and

Han, Entity linking with a knowledge base: Issues, techniques, and solutions, TKDE 27(2) (2015), 443–460.

78.

Sozio and

Gionis, The community-search problem and how to plan a successful cocktail party, in: KDD, 2010, pp. 939–948.

79.

Steiner,

van Hooland and

Summers, MJ no more: Using concurrent Wikipedia edit spikes with social network plausibility checks for breaking news detection, in: WWW Companion, 2013, pp. 791–794. doi:10.1145/2487788.2488049.

80.

Stilo and Velardi , Efficient temporal mining of micro-blog texts and its application to event discovery, DAMI 30(2) (2016), 372–402.

81.

Stilo and

Velardi, Time makes sense: Event discovery in Twitter using temporal similarity, in: IEEE/WIC/ACM WI, 2014, pp. 186–193.

82.

Swan, Sensor mania! The Internet of Things, wearable computing, objective metrics, and the quantified self 2.0, Journal of Sensor and Actuator Networks 1(3) (2012), 217–253. doi:10.3390/jsan1030217.

83.

Tang and

C.C.

Yang, TUT: A statistical model for detecting trends, topics and user interests in social media, in: CIKM, 2012, pp. 972–981. doi:10.1145/2396761.2396884.

84.

N.A.

Thapen,

D.S.

Simmie and

Hankin, The early bird catches the term: Combining Twitter and news data for event detection and situational awareness, CoRR (2015) arXiv:abs/1504.02335.

85.

Tsourakakis,

Bonchi,

Gionis,

Gullo and

Tsiarli, Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees, in: KDD, 2013, pp. 104–112.

86.

Valari,

Kontaki and

A.N.

Papadopoulos, Discovery of top-k dense subgraphs in dynamic graph collections, in: SSDBM, 2012, pp. 213–230.

87.

Vieweg,

Castillo and

Imran, Integrating Social Media Communications into the Rapid Assessment of Sudden Onset Disasters, Springer International Publishing, Cham, 2014, pp. 444–461.

88.

Vosoughi and

Roy, A semi-automatic method for efficient detection of stories on social media, in: ICWSM, 2016, pp. 707–710.

89.

J.B.P.

Vuurens and

A.P.

de Vries, First story detection using multiple nearest neighbors, in: SIGIR, 2016, pp. 845–848. doi:10.1145/2911451.2914761.

90.

Weiler,

Grossniklaus and

M.H.

Scholl, Evaluation measures for event detection techniques on Twitter data streams, in: BICOD, 2015, pp. 108–119.

91.

Weiler,

Grossniklaus and

M.H.

Scholl, Editorial: Survey and experimental analysis of event detection techniques for Twitter, The Computer Journal.

92.

Weng and

B.-S.

Lee, Event detection in Twitter, in: ICWSM, 2011.

93.

A.W.

Williams,

S.M.

Pertet and

Narasimhan, Tiresias: Black-box failure prediction in distributed systems, in: IPDPS, 2007, pp. 41–50.

94.

Wu,

Cheng,

Ke,

Huang,

Yan and

Wu, Core decomposition in large temporal graphs, in: IEEE BigData, 2015, pp. 649–658.

95.

Xiao,

Rozenshtein and

Gionis, Discovering topically- and temporally-coherent events in interaction networks, in: ECML-PKDD, 2016, pp. 690–705.

96.

Zhang,

Zhou,

Yuan,

Zhuang,

Zheng,

Kaplan,

Wang and

Han, GeoBurst: Real-time local event detection in geo-tagged tweet streams, in: SIGIR, 2016, pp. 513–522. doi:10.1145/2911451.2911519.

97.

Zhao,

Zhang,

Lu and

Zhang, STeller: An approach for context-aware story detection using different similarity metrics and dense subgraph mining, in: CSCWD, 2016, pp. 152–157.

98.

Zhao,

T.-Y.

Liu,

S.S.

Bhowmick and

W.-Y.

Ma, Event detection from evolution of click-through data, in: KDD, 2006, pp. 484–493.