Individual and Collective Graph Mining: Principles, Algorithms, and Applications | SpringerLink
Skip to main content
Springer Nature Link
Log in

Individual and Collective Graph Mining

Principles, Algorithms, and Applications

  • Book
  • © 2018

Overview

Authors:
  1. Danai Koutra

    1. University of Michigan, Ann Arbor, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Christos Faloutsos

    1. Carnegie Mellon University, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • 668 Accesses

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook JPY 6863
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book JPY 8579
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

Graphs naturally represent information ranging from links between web pages, to communication in email networks, to connections between neurons in our brains. These graphs often span billions of nodes and interactions between them. Within this deluge of interconnected data, how can we find the most important structures and summarize them? How can we efficiently visualize them? How can we detect anomalies that indicate critical events, such as an attack on a computer system, disease formation in the human brain, or the fall of a company?

This book presents scalable, principled discovery algorithms that combine globality with locality to make sense of one or more graphs. In addition to fast algorithmic methodologies, we also contribute graph-theoretical ideas and models, and real-world applications in two main areas:

  • Individual Graph Mining: We show how to interpretably summarize a single graph by identifying its important graph structures. We complement summarization with inference, which leverages information about few entities (obtained via summarization or other methods) and the network structure to efficiently and effectively learn information about the unknown entities.
  • Collective Graph Mining: We extend the idea of individual-graph summarization to time-evolving graphs, and show how to scalably discover temporal patterns. Apart from summarization, we claim that graph similarity is often the underlying problem in a host of applications where multiple graphs occur (e.g., temporal anomaly detection, discovery of behavioral patterns), and we present principled, scalable algorithms for aligning networks and measuring their similarity.
The methods that we present in this book leverage techniques from diverse areas, such as matrix algebra, graph theory, optimization, information theory, machine learning, finance, and social science,to solve real-world problems. We present applications of our exploration algorithms to massive datasets, including a Web graph of 6.6 billion edges, a Twitter graph of 1.8 billion edges, brain graphs with up to 90 million edges, collaboration, peer-to-peer networks, browser logs, all spanning millions of users and interactions.

Table of contents (7 chapters)

  1. Front Matter

    Pages i-xi
    Download chapter PDF

  2. Introduction

    • Danai Koutra, Christos Faloutsos
    Pages 1-13

  3. Individual Graph Mining

    1. Front Matter

      Pages 15-15
      Download chapter PDF

    2. Summarization of Static Graphs

      • Danai Koutra, Christos Faloutsos
      Pages 17-48

    3. Inference in a Graph

      • Danai Koutra, Christos Faloutsos
      Pages 49-72

  4. Collective Graph Mining

    1. Front Matter

      Pages 73-73
      Download chapter PDF

    2. Summarization of Dynamic Graphs

      • Danai Koutra, Christos Faloutsos
      Pages 75-95

    3. Graph Similarity

      • Danai Koutra, Christos Faloutsos
      Pages 97-141

    4. Graph Alignment

      • Danai Koutra, Christos Faloutsos
      Pages 143-165

    5. Conclusions and Further Research Problems

      • Danai Koutra, Christos Faloutsos
      Pages 167-169

  5. Back Matter

    Pages 171-194
    Download chapter PDF
Back to top

Authors and Affiliations

  • University of Michigan, Ann Arbor, USA

    Danai Koutra

  • Carnegie Mellon University, USA

    Christos Faloutsos

About the authors

Danai Koutra is an Assistant Professor in Computer Science and Engineering at University of Michigan, Ann Arbor. Her research interests include large-scale graph mining, graph similarity and matching, graph summarization, and anomaly detection. Danai’s research has been applied mainly to social, collaboration, and web networks, as well as brain connectivity graphs. She holds one ""rate-1"" patent and has six (pending) patents on bipartite graph alignment. Danai won the 2016 ACM SIGKDD Dissertation award, and an honorable mention for the SCS Doctoral Dissertation Award (CMU). She has multiple papers in top data mining conferences, including two award-winning papers, she has given three tutorials, and her work has been covered by the popular press, such as the MIT Technology Review. She has worked at IBM Watson, Microsoft Research, and Technicolor. She earned her Ph.D. and M.S. in Computer Science from CMU in 2015 and her diploma in Electrical and Computer Engineering at the National Technical University of Athens in 2010.Christos Faloutsos is a Professor at Carnegie Mellon University. He has received the Presidential Young Investigator Award by the National Science Foundation (1989), the Research Contributions Award in ICDM 2006, the SIGKDD Innovations Award (2010), 24 ""best paper"" awards (including 5 ""test of time"" awards), and 4 teaching awards. Six of his advisees have attracted KDD or SCS dissertation awards, He is an ACM Fellow, he has served as a member of the executive committee of SIGKDD; he has published over 350 refereed articles, 17 book chapters, and 2 monographs. He holds seven patents (and 2 pending), and he has given over 40 tutorials and over 20 invited distinguished lectures. His research interests include large-scale data mining with emphasis on graphs and time sequences; anomaly detection, tensors, and fractals.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation