Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article
Public Access

Narrative Maps: An Algorithmic Approach to Represent and Extract Information Narratives

Published: 05 January 2021 Publication History

Abstract

Narratives are fundamental to our perception of the world and are pervasive in all activities that involve the representation of events in time. Yet, modern online information systems do not incorporate narratives in their representation of events occurring over time. This article aims to bridge this gap, combining the theory of narrative representations with the data from modern online systems. We make three key contributions: a theory-driven computational representation of narratives, a novel extraction algorithm to obtain these representations from data, and an evaluation of our approach. In particular, given the effectiveness of visual metaphors, we employ a route map metaphor to design a narrative map representation. The narrative map representation illustrates the events and stories in the narrative as a series of landmarks and routes on the map. Each element of our representation is backed by a corresponding element from formal narrative theory, thus providing a solid theoretical background to our method. Our approach extracts the underlying graph structure of the narrative map using a novel optimization technique focused on maximizing coherence while respecting structural and coverage constraints. We showcase the effectiveness of our approach by performing a user evaluation to assess the quality of the representation, metaphor, and visualization. Evaluation results indicate that the Narrative Map representation is a powerful method to communicate complex narratives to individuals. Our findings have implications for intelligence analysts, computational journalists, and misinformation researchers.

References

[1]
H Porter Abbott. 2008. The Cambridge introduction to narrative .Cambridge University Press, One Liberty Plaza, New York, NY, USA.
[2]
James Abello, Frank Van Ham, and Neeraj Krishnan. 2006. Ask-graphview: A large scale graph visualization system. IEEE transactions on visualization and computer graphics, Vol. 12, 5 (2006), 669--676.
[3]
Jeffery Ansah, Lin Liu, Wei Kang, Selasie Kwashie, Jixue Li, and Jiuyong Li. 2019. A Graph is Worth a Thousand Words: Telling Event Stories Using Timeline Summarization Graphs. In The World Wide Web Conference (WWW '19). ACM, New York, NY, USA, 2565--2571.
[4]
Chris Baber, Dan Andrews, Tom Duffy, and Richard McMaster. 2011. Sensemaking as narrative: Visualization for collaboration. VAW2011, University London College, Vol. VAW2011 (2011), 7--8.
[5]
Roland Barthes and Lionel Duisit. 1975. An Introduction to the Structural Analysis of Narrative. New Literary History, Vol. 6, 2 (1975), 237--272.
[6]
Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, Vol. 353, 6295 (2016), 163--166.
[7]
Kenneth Burke. 1969. A grammar of motives . Vol. 177. Univ of California Press, 155 Grand Ave. Suite 400. Oakland, CA.
[8]
Remo Aslak Burkhard and Michael Meier. 2005. Tube Map Visualization: Evaluation of a Novel Knowledge Visualization Application for the Transfer of Knowledge in Long-Term Projects. J. UCS, Vol. 11, 4 (2005), 473--494.
[9]
Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St. John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. 2018. Universal Sentence Encoder. CoRR, Vol. abs/1803.11175 (2018), 1--7. arxiv: 1803.11175
[10]
Hao-Fei Cheng, Ruotong Wang, Zheng Zhang, Fiona O'Connell, Terrance Gray, F. Maxwell Harper, and Haiyi Zhu. 2019. Explaining Decision-Making Algorithms through UI: Strategies to Help Non-Expert Stakeholders. In Proc. of the 2019 CHI Conference on Human Factors in Computing Systems (CHI '19). ACM, New York, NY, USA, 1--12.
[11]
Giovanni Luca Ciampaglia. 2018. Fighting fake news: a role for computational social science in the fight against digital misinformation. Journal of Computational Social Science, Vol. 1, 1 (2018), 147--153.
[12]
Sarah Cohen, James T Hamilton, and Fred Turner. 2011. Computational journalism. Commun. ACM, Vol. 54, 10 (2011), 66--71.
[13]
Robert P Dilworth. 1987. A Decomposition Theorem for Partially Ordered Sets .Birkh"auser Boston, Boston, MA, 139--144.
[14]
Peter Eades and Mao Lin Huang. 2004. Navigating Clustered Graphs Using Force-Directed Methods. In Graph Algorithms and Applications 2 . World Scientific, 5 Toh Tuck Link, Singapore, 596224, Singapore, 191--215.
[15]
John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull. 2004. Graphviz and Dynagraph -- Static and Dynamic Graph Drawing Tools. In Graph Drawing Software, Michael Jünger and Petra Mutzel (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 127--148.
[16]
Christos Faloutsos, Kevin S. McCurley, and Andrew Tomkins. 2004. Fast Discovery of Connection Subgraphs. In Proc. of the Tenth ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD '04). ACM, New York, NY, USA, 118--127.
[17]
Jonathan P. Forsyth, Rachel M. Bittner, Michael Musick, and Juan P. Bello. 2015. Improving and adapting finite state transducer methods for musical accompaniment. In 41st Int. Computer Music Conf., ICMC 2015, Richard Dudas (Ed.). Int. Computer Music Association, Denton, TX, 290--297.
[18]
Emden R Gansner, Yehuda Koren, and Stephen C North. 2005. Topological fisheye views for visualizing large graphs. IEEE Transactions on Visualization and Computer Graphics, Vol. 11, 4 (2005), 457--468.
[19]
Emden R Gansner, Eleftherios Koutsofios, Stephen C North, and K-P Vo. 1993. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, Vol. 19, 3 (1993), 214--230.
[20]
Félix Garc'ia, Mª Ángeles Moraga, Manuel Serrano, and Mario Piattini. 2015. Visualisation environment for global software development management. IET Software, Vol. 9, 2 (2015), 51--64.
[21]
Gérard Genette. 1983. Narrative discourse: An essay in method . Vol. 3. Cornell University Press, 512 East State St., Ithaca, NY.
[22]
Ilka H Gleibs. 2017. Are all 'research fields' equal' Rethinking practice for the use of data from crowdsourcing market places. Behavior Research Methods, Vol. 49, 4 (2017), 1333--1342.
[23]
Fethallah Hadjila, Amine Belabed, and Mohammed Merzoug. 2019. Flexible service discovery based on multiple matching algorithms. Int. Journal of Web Engineering and Technology, Vol. 14, 4 (2019), 315--340.
[24]
Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008. Exploring network structure, dynamics, and function using NetworkX . Technical Report. Los Alamos National Lab. (LANL).
[25]
Jeffry Halverson, Steven Corman, and H Lloyd Goodall. 2011. Master narratives of Islamist extremism .Springer, 175 5th Ave., New York, NY, USA.
[26]
David Hauser, Gabriele Paolacci, and Jesse J Chandler. 2018. Common Concerns with MTurk as a Participant Pool: Evidence and Solutions.
[27]
Jinwon Ho and Rong Tang. 2001. Towards an Optimal Resolution to Information Overload: An Infomediary Approach. In Proc. of the 2001 Int. ACM SIGGROUP Conference on Supporting Group Work (GROUP '01). ACM, New York, NY, USA, 91--96.
[28]
Thore Husfeldt. 1995. Fully Dynamic Transitive Closure in plane dags with one source and one sink. In Algorithms -- ESA '95, Paul Spirakis (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 199--212.
[29]
Dongwoo Kim and Alice Oh. 2011. Topic Chains for Understanding a News Corpus. In Computational Linguistics and Intelligent Text Processing, Alexander Gelbukh (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 163--176.
[30]
Catherine Kohler Riessman. 2000. Analysis of personal narratives. In Qualitative research in social work . Columbia University Press, 61 West 62 St., New York, NY, USA, Chapter 7, 168--191.
[31]
Walter S. Lasecki, Mitchell Gordon, Danai Koutra, Malte F. Jung, Steven P. Dow, and Jeffrey P. Bigham. 2014. Glance: Rapidly Coding Behavioral Video with the Crowd. In Proc. of the 27th Annual ACM Symposium on User Interface Software and Technology (UIST '14). ACM, New York, NY, USA, 551--562.
[32]
Tianyi Li, Chandler J Manns, Chris North, and Kurt Luther. 2019. Dropping the baton? Understanding errors and bottlenecks in a crowdsourced sensemaking pipeline. Proceedings of the ACM on Human-Computer Interaction, Vol. 3, CSCW (2019), 1--26.
[33]
Tianyi Li, Asmita Shah, Kurt Luther, and Chris North. 2018. Crowdsourcing Intelligence Analysis with Context Slices. In CHI 2018 Sensemaking Workshop .
[34]
Bang Liu, Di Niu, Kunfeng Lai, Linglong Kong, and Yu Xu. 2017. Growing Story Forest Online from Massive Breaking News. In Proc. of the 2017 ACM on Conference on Information and Knowledge Management (CIKM '17). ACM, New York, NY, USA, 777--785.
[35]
Leland McInnes, John Healy, and Steve Astels. 2017. hdbscan: Hierarchical density based clustering. Journal of Open Source Software, Vol. 2, 11 (2017), 205.
[36]
Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426.
[37]
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science, Vol. 298, 5594 (2002), 824--827.
[38]
Alister Miskimmon, Ben O'loughlin, and Laura Roselle. 2014. Strategic narratives: Communication power and the new world order .Routledge, 711 3rd Ave. #8, New York, NY, USA.
[39]
Alister Miskimmon, Ben O'Loughlin, and Laura Roselle. 2017. Forging the world: Strategic narratives and international relations .University of Michigan Press, 839 Greene St., Ann Arbor, MI.
[40]
Tanushree Mitra and Eric Gilbert. 2015. CREDBANK: A Large-Scale Social Media Corpus With Associated Credibility Annotations. Int. AAAI Conf. on Web and Social Media, Vol. 2015 (2015), 258--267.
[41]
Tanushree Mitra, C.J. Hutto, and Eric Gilbert. 2015. Comparing Person- and Process-Centric Strategies for Obtaining Quality Data on Amazon Mechanical Turk. In Proc. of the 33rd Annual ACM Conference on Human Factors in Computing Systems (CHI '15). ACM, New York, NY, USA, 1345--1354.
[42]
Ramesh Nallapati, Ao Feng, Fuchun Peng, and James Allan. 2004. Event Threading within News Topics. In Proc. of the Thirteenth ACM Int. Conf. on Information and Knowledge Management (CIKM '04). ACM, New York, NY, USA, 446--453.
[43]
Alexis R Neigel, Justine P Caylor, Sue E Kase, Michelle T Vanni, and Jefferson Hoye. 2018. The role of trust and automation in an intelligence analyst decisional guidance paradigm. Journal of Cognitive Engineering and Decision Making, Vol. 12, 4 (2018), 239--247.
[44]
A. Conrad Nied, Leo Stewart, Emma Spiro, and Kate Starbird. 2017. Alternative Narratives of Crisis Events: Communities and Social Botnets Engaged on Social Media. In Companion of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW '17 Companion). ACM, New York, NY, USA, 263--266.
[45]
Brian Keith Norambuena, Michael Horning, and Tanushree Mitra. 2020. Evaluating the Inverted Pyramid Structure through Automatic 5W1H Extraction and Summarization. In Proc. of the 2020 Computation
[46]
Journalism Symposium. Computation
[47]
Journalism 2020, Boston, MA, USA, 1--7.
[48]
Gabriele Paolacci, Jesse Chandler, and Panagiotis G Ipeirotis. 2010. Running experiments on amazon mechanical turk. Judgment and Decision making, Vol. 5, 5 (2010), 411--419.
[49]
Wim Pijls and Rob Potharst. 2013. Another Note on Dilworth's Decomposition Theorem. Journal of Discrete Mathematics, Vol. 2013 (2013), 692--645.
[50]
Kent Puckett. 2016. Narrative theory .Cambridge University Press, One Liberty Plaza, New York, NY, USA.
[51]
Shlomith Rimmon-Kenan. 2003. Narrative fiction: Contemporary poetics .Routledge, 711 3rd Ave. #8, New York, NY, USA.
[52]
Corina Robbins. 2019. The Weaponization of Social Media . Technical Report. Mercy Corps.
[53]
Laura Roselle, Alister Miskimmon, and Ben O?Loughlin. 2014. Strategic narrative: A new means to understand soft power. Media, War & Conflict, Vol. 7, 1 (2014), 70--84.
[54]
Niloufar Salehi, Lilly C. Irani, Michael S. Bernstein, Ali Alkhatib, Eva Ogbe, Kristy Milland, and Clickhappier. 2015. We Are Dynamo: Overcoming Stalling and Friction in Collective Action for Crowd Workers. In Proc. of the 33rd Annual ACM Conference on Human Factors in Computing Systems (CHI '15). ACM, New York, NY, USA, 1621--1630.
[55]
Dafna Shahaf and Carlos Guestrin. 2010. Connecting the Dots between News Articles. In Proc. of the 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD '10). ACM, New York, NY, USA, 623--632.
[56]
Dafna Shahaf and Carlos Guestrin. 2012. Connecting two (or less) dots: Discovering structure in news articles. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 5, 4 (2012), 1--31.
[57]
Dafna Shahaf, Carlos Guestrin, and Eric Horvitz. 2012. Trains of Thought: Generating Information Maps. In Proc. of the 21st Int. Conf. on World Wide Web (WWW '12). ACM, New York, NY, USA, 899--908.
[58]
Dafna Shahaf, Carlos Guestrin, and Eric Horvitz. 2013a. Metro Maps of Information. SIGWEB Newsl., Vol. Spring, Article 4 (2013), bibinfonumpages9 pages.
[59]
Dafna Shahaf, Carlos Guestrin, Eric Horvitz, and Jure Leskovec. 2015. Information cartography. Commun. ACM, Vol. 58, 11 (2015), 62--73.
[60]
Dafna Shahaf, Jaewon Yang, Caroline Suen, Jeff Jacobs, Heidi Wang, and Jure Leskovec. 2013b. Information Cartography: Creating Zoomable, Large-Scale Maps of Information. In Proc. of the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD '13). ACM, New York, NY, USA, 1097--1105.
[61]
Azra Shamim, Vimala Balakrishnan, and Muhammad Tahir. 2015. Evaluation of opinion visualization techniques. Information visualization, Vol. 14, 4 (2015), 339--358.
[62]
Barbara Herrnstein Smith. 1980. Narrative versions, narrative theories. Critical inquiry, Vol. 7, 1 (1980), 213--236.
[63]
Sandeep Soni, Tanushree Mitra, Eric Gilbert, and Jacob Eisenstein. 2014. Modeling Factuality Judgments in Social Media Text. In Proc. of the 52nd Annual Meeting of the ACL (Volume 2: Short Papers). ACL, Baltimore, Maryland, 415--420.
[64]
Joanna Szostek. 2017. Defence and Promotion of Desired State Identity in Russia's Strategic Narrative. Geopolitics, Vol. 22, 3 (2017), 571--593.
[65]
Barbara Tversky. 2004. Narratives of Space, Time, and Life. Mind & Language, Vol. 19, 4 (2004), 380--392.
[66]
Lu Wang, Claire Cardie, and Galen Marchetti. 2015. Socially-Informed Timeline Generation for Complex Events. In Proc. of the 2015 Conference of the North American Chapter of the ACL: Human Language Technologies . ACL, Denver, Colorado, 1055--1065.
[67]
Jen Weedon, William Nuland, and Alex Stamos. 2017. Information operations and Facebook . Technical Report. Facebook.
[68]
Vanessa Williamson. 2016. On the ethics of crowdsourced research. PS: Political Science & Politics, Vol. 49, 1 (2016), 77--81.
[69]
Tom Wilson, Kaitlyn Zhou, and Kate Starbird. 2018. Assembling strategic narratives: Information operations as collaborative work within an online community. Proc. of the ACM on HCI, Vol. 2, CSCW (2018), 1--26.
[70]
Sarah E. Worth. 2008. Storytelling and Narrative Knowing: An Examination of the Epistemic Benefits of Well-Told Stories. Journal of Aesthetic Education, Vol. 42, 3 (2008), 42--56.
[71]
Shize Xu, Shanshan Wang, and Yan Zhang. 2013. Summarizing Complex Events: a Cross-Modal Solution of Storylines Extraction and Reconstruction. In Proc. of the 2013 Conference on Empirical Methods in Natural Language Processing. ACL, Seattle, Washington, USA, 1281--1291.
[72]
Rui Yan, Xiaojun Wan, Jahna Otterbacher, Liang Kong, Xiaoming Li, and Yan Zhang. 2011. Evolutionary Timeline Summarization: A Balanced Optimization Framework via Iterative Substitution. In Proc. of the 34th Int. ACM SIGIR Conference on Research and Development in Info. Retrieval (SIGIR '11). ACM, New York, NY, USA, 745--754.
[73]
Christopher C Yang, Xiaodong Shi, and Chih-Ping Wei. 2009. Discovering event evolution graphs from news corpora. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol. 39, 4 (2009), 850--863.
[74]
Amy X. Zhang, Lea Verou, and David Karger. 2017. Wikum: Bridging Discussion Forums and Wikis Using Recursive Summarization. In Proc. of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW '17). ACM, New York, NY, USA, 2082--2096.
[75]
Houkui Zhou, Huimin Yu, Roland Hu, and Junguo Hu. 2017. A survey on trends of cross-media topic evolution map. Knowledge-Based Systems, Vol. 124 (2017), 164--175.
[76]
P. Zhou, B. Wu, and Z. Cao. 2017. EMMBTT: A Novel Event Evolution Model Based on TFxIEF and TDC in Tracking News Streams. In 2017 IEEE Second Int. Conf. on Data Science in Cyberspace (DSC) . IEEE, Shenzhen, China, 102--107.

Cited By

View all
  • (2025)A Multimodal Dataset of Fact-Checked News from Chile’s Constitutional Processes: Collection, Processing, and AnalysisData10.3390/data1002001310:2(13)Online publication date: 28-Jan-2025
  • (2025)CoRBS: a dynamic storytelling algorithm using a novel contextualization approach for documents utilizing BERT featuresKnowledge and Information Systems10.1007/s10115-024-02263-867:2(1213-1248)Online publication date: 1-Feb-2025
  • (2024)Structured Life Narratives: Building Life Story Hierarchies with Graph-Enhanced Event Feature RefinementApplied Sciences10.3390/app1402091814:2(918)Online publication date: 22-Jan-2024
  • Show More Cited By

Index Terms

  1. Narrative Maps: An Algorithmic Approach to Represent and Extract Information Narratives

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Proceedings of the ACM on Human-Computer Interaction
      Proceedings of the ACM on Human-Computer Interaction  Volume 4, Issue CSCW3
      CSCW
      December 2020
      1825 pages
      EISSN:2573-0142
      DOI:10.1145/3446568
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 05 January 2021
      Published in PACMHCI Volume 4, Issue CSCW3

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. antichains
      2. information
      3. narrative maps

      Qualifiers

      • Research-article

      Funding Sources

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)923
      • Downloads (Last 6 weeks)80
      Reflects downloads up to 17 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)A Multimodal Dataset of Fact-Checked News from Chile’s Constitutional Processes: Collection, Processing, and AnalysisData10.3390/data1002001310:2(13)Online publication date: 28-Jan-2025
      • (2025)CoRBS: a dynamic storytelling algorithm using a novel contextualization approach for documents utilizing BERT featuresKnowledge and Information Systems10.1007/s10115-024-02263-867:2(1213-1248)Online publication date: 1-Feb-2025
      • (2024)Structured Life Narratives: Building Life Story Hierarchies with Graph-Enhanced Event Feature RefinementApplied Sciences10.3390/app1402091814:2(918)Online publication date: 22-Jan-2024
      • (2024)Lost in Recursion: Mining Rich Event Semantics in Knowledge GraphsProceedings of the 16th ACM Web Science Conference10.1145/3614419.3644001(354-364)Online publication date: 21-May-2024
      • (2024)TimeFlows: Visualizing Process Chronologies from Vast Collections of Heterogeneous Information ObjectsResearch Challenges in Information Science10.1007/978-3-031-59465-6_13(203-219)Online publication date: 2-May-2024
      • (2023)A Survey on Event-Based News Narrative ExtractionACM Computing Surveys10.1145/358474155:14s(1-39)Online publication date: 17-Jul-2023
      • (2023)Synthetic Lies: Understanding AI-Generated Misinformation and Evaluating Algorithmic and Human SolutionsProceedings of the 2023 CHI Conference on Human Factors in Computing Systems10.1145/3544548.3581318(1-20)Online publication date: 19-Apr-2023
      • (2023)Entity graphs for exploring online discourseKnowledge and Information Systems10.1007/s10115-023-01877-865:9(3591-3609)Online publication date: 24-Apr-2023
      • (2022)Design guidelines for narrative maps in sensemaking tasksInformation Visualization10.1177/1473871622107959321:3(220-245)Online publication date: 2-Mar-2022
      • (2022)English Machine Translation System based on Human-Computer Interaction Algorithm2022 IEEE 2nd International Conference on Mobile Networks and Wireless Communications (ICMNWC)10.1109/ICMNWC56175.2022.10031762(1-4)Online publication date: 2-Dec-2022
      • Show More Cited By

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Full Access

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media