Home / Topics

Graph Mining and Social Networks

Curated by: Christos Faloutsos

Have you ever wondered how Google finds the best page for your question? How would you spot the most important people on faceBook? How would you spot fake followers on Twitter? In a who-contacts- whom network, which is the best nodes to immunize, to stop a flu epidemic?

All these problems, and myriad more, use “graph mining” methods. But graph mining is not restricted to social networks: in computer-to- computer communication networks we want to find whether a computer is under cyber-attack (and protect it, before-hand); in a user-product review system, we want to find fake reviews; in a prey-predator ecological system, we want to find the most important species, to protect the system from unraveling.

Graph mining uses sophisticated mathematical methods (“linear algebra”, “eigenvalue analysis”, “matrix factorizations”, “tensors”), which pay off spectacularly - Google’s PageRank algorithm being the most obvious example.

Link: http://www.cs.cmu.edu/~christos/TALKS/16-graph-mining-intro-kdd/

For K-12

  • Ever wondered how the characters of 'Les Miserables' relate to each other? If yes, check this interactive animation!
  • Do you have a facebook account? do you want to know how the people are connected, over the globe? facebook image

For CS professionals

  • Do you want to learn more about graph analytics? Check this book (free, from most libraries and *.edu accounts, in the US)
  • Do you want to try your graph analytics algorithms, on real data? Check these wonderful collections
    • The KONECT collection at Koblenz University
    • The SNAP collection at Stanford

Related KDD2016 Papers

Title & Authors
Approximate Personalized PageRank on Dynamic Graphs
Author(s): Hongyang Zhang*, Stanford University; Peter Lofgren, Stanford University
Compact and Scalable Graph Neighborhood Sketching
Author(s): Takuya Akiba*, NII; Yosuke Yano, National Institute of Informatics
Structural Neighborhood based Classification of Nodes in a Network
Author(s): Sharad Nandanwar*, Indian Institute of Science; Musti Narasimha Murty, Indian Institute of Science
User Identity Linkage by Latent User Space Modelling
Author(s): Xin Mu*, Nanjing University; Feida Zhu, Singapore Management Univ.; Zhi-Hua Zhou, ; Ee-Peng Lim, Singapore Management University; Jing Xiao, ; Jianzong Wang,
Kam1n0: MapReduce-based Assembly Clone Search for Reverse Engineering
Author(s): Steven H. H. Ding, McGill University; Benjamin C. M. Fung*, McGill University; Philippe Charland, Defence Research and Development Canada
Joint Community and Structural Hole Spanner Detection via Harmonic Modularity
Author(s): Lifang He*, ; CHUN-TA LU, UIC; Jiaqi Ma, Tsinghua University; Jianping Cao, NUDT; Linlin Shen, ; Philip S. Yu, UI Chicago
Burstiness Scale: a highly parsimonious model forcharacterizing random series of events
Author(s): Rodrigo Alves*, CEFET-MG; Renato Assunção, DCC-UFMG; Pedro O.S. Vaz de Melo, DCC-UFMG
Talent Circle Detection in Job Transition Networks
Author(s): Huang Xu*, Northwestern Polytechnical Uni; Jingyuan Yang, Rutgers University; zhi wen Yu, ; Hui Xiong, Rutgers; Hengshu Zhu, Baidu Inc.
Sampling of Attributed Networks From Hierarchical Generative Models
Author(s): Pablo Robles Granda*, Purdue University; Sebastian Moreno, ; Jennifer Neville, Purdue
FINAL: Fast Attributed Network Alignment
Author(s): Si Zhang*, Arizona State University; Hanghang Tong, Arizona State University
FASCINATE: Fast Cross-Layer Dependency Inference on Multi-layered Networks
Author(s): Chen Chen*, Arizona State Unversity; Hanghang Tong, Arizona State University; Lei Xie, City University of New York; Lei YIng, Arizona State University; Qing He, Arizona State University
Finding Gangs in War from Signed Networks
Author(s): Lingyang Chu*, Simon Fraser University; Zhefeng Wang, University of Science and Technology of China; Jian Pei, Simon Fraser University; Jiannan Wang, Simon Fraser University; Zijin Zhao, Simon Fraser University; Enhong Chen,
Engagement Capacity and Engaging Team Formation for Reach Maximization of Online Social Media Platfo
Author(s): Alexander Nikolaev*, University at Buffalo; Shounak Gore, University at Buffalo; Venu Govindaraju, University at Buffalo
QUINT: On Query-Specific Optimal Networks
Author(s): Liangyue Li*, Arizona State University; Yuan Yao, Nanjing University; Jie Tang, Tsinghua University; Wei Fan, Baidu; Hanghang Tong, Arizona State University
Dynamics of Large Multi-View Social Networks: Synergy, Cannibalization and Cross-View Interplay
Author(s): Yu Shi*, UIUC; Myunghwan Kim, LinkedIn Corporation; Shaunak Chatterjee, LinkedIn Corporation; Mitul Tiwari, LinkedIn Corporation; Souvik Ghosh, LinkedIn; Romer Rosales, LinkedIn
Ranking Universities Based on Career Outcomes of Graduates
Author(s): Navneet Kapur (GoFundMe), Nikita Lytkin (LinkedIn Corporation), Bee-Chung Chen (LinkedIn Corporation), Deepak Agarwal (LinkedIn Corporation), Igor Perisic (LinkedIn Corporation)
Come-and-Go Patterns of Group Evolution: A Dynamic Model
Author(s): Tianyang Zhang*, Tsinghua University; Peng Cui, Tsinghua University; Christos Faloutsos, Carnegie Mellon University; Wenwu Zhu, Tsinghua University; Shiqiang Yang,
node2vec: Scalable Feature Learning for Networks
Author(s): Aditya Grover*, Stanford University; Jure Leskovec, Stanford University
Meta Structure: Computing Relevance in Large Heterogeneous Information Networks
Author(s): Zhipeng Huang*, University of Hong Kong; Yudian Zheng, The University of Hong Kong; Reynold Cheng, ; Yizhou Sun, Northeastern Univ; Nikos Mamoulis, ; Xiang Li, The University of Hong Kong
Reconstructing an Epidemic over Time
Author(s): Polina Rozenshtein, Aalto University; Aristides Gionis*, Aalto University; B. Aditya Prakash, Virginia Tech; Jilles Vreeken, Max-Planck Institute for Informatics and Saarland University
Identifying Decision Makers from Professional Social Networks
Author(s): Shipeng Yu*, LinkedIn; Evangelia Christakopoulou, University of Minnesota; Abhishek Gupta, LinkedIn
A Truth Discovery Approach with Theoretical Guarantee
Author(s): Houping Xiao*, SUNY Buffalo; Jing Gao, ; Zhaoran Wang, Princeton University; Shiyu Wang, UIUC; Lu Su, SUNY Buffalo; Han Liu, Princeton University
Smart broadcasting: Do you want to be seen?
Author(s): Erfan Tavakoli, Sharif University; Mohammad Reza Karimi, Sharif University; Mehrdad Farajtabar, Georgia Tech; Le Song, ; Manuel Gomez-Rodriguez*, MPI-SWS
When Social Influence Meets Item Inference
Author(s): Hui-Ju Hung, Pennsylvania State University; Hong-Han Shuai, Academia Sinica; De-Nian Yang*, Academic Sinica; Liang-Hao Huang, Academia Sinica; Wang-Chien Lee, The Pennsylvania State University; Jian Pei, Simon Fraser University; Ming-Syan Chen, National Taiwan University
A multiple test correction for streams and cascades of statistical hypothesis tests
Author(s): Geoff Webb*, Monash University; Francois Petitjean, Monash
Effcient Processing of Network Proximity Queries via Chebyshev Acceleration
Author(s): Mustafa Coskun*, Case Western University; Ananth Grama, ; Mehmet Koyuturk,
Robust Influence Maximization
Author(s): Xinran He*, University of Southern California; David Kempe, University of Southern California
How to Compete Online for News Audience: Modeling Words that Attract Clicks
Author(s): Joon Hee Kim*, KAIST; Amin Mantrach, Yahoo! Research; Alex Jaimes, Yahoo!; Alice Oh, Korea Advanced Institute of Science and Technology
CatchTartan: Representing and Summarizing Dynamic Multicontextual Behaviors
Author(s): Meng Jiang*, UIUC; Christos Faloutsos, Carnegie Mellon University; Jiawei Han, University of Illinois at Urbana-Champaign
Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
Author(s): Emaad Manzoor, Stony Brook University; Leman Akoglu*, SUNY Stony Brook
Asymmetric Transitivity Preserving Graph Embedding
Author(s): Mingdong Ou*, Tsinghua University; Peng Cui, Tsinghua University; Jian Pei, Simon Fraser University; Wenwu Zhu, Tsinghua University
The Limits of Popularity-Based Recommendations, and the Role of Social Ties
Author(s): Marco Bressan*, Sapienza University of Rome; Stefano Leucci, Sapienza University of Rome; Alessandro Panconesi, Sapienza University of Rome; Prabhakar Raghavan, Google; Erisa Terolli, Sapienza University of Rome
Structural Deep Network Embedding
Author(s): DAIXIN WANG*, TSINGHUA UNIVERSITY; Peng Cui, Tsinghua University; Wenwu Zhu, Tsinghua University
ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
Author(s): Matteo Riondato*, Two Sigma Investments; Eli Upfal, Brown University
PTE: Enumerating Trillion Triangles On Distributed Systems
Author(s): Ha-Myung Park*, KAIST; Sung-Hyon Myaeng, KAIST; U Kang, Seoul National University
Scalable Betweenness Centrality Maximization via Sampling
Author(s): Ahmad Mahmoody*, Brown University; Eli Upfal, Brown University; Charalampos Tsourakakis, Harvard
Robust Influence Maximization
Author(s): Wei Chen, Microsoft Research; Tian Lin*, Tsinghua University; Zihan Tan, IIIS, Tsinghua University; Mingfei Zhao, IIIS, Tsinghua University; Xuren Zhou, The Hong Kong University of Science and Technology
Graph Wavelets via Sparse Cuts
Author(s): Arlei Lopes da Silva*, UC, Santa Barbara; Xuan-Hong Dang, UCSB; Prithwish Basu, Raytheon BBN; Ambuj Singh, UCSB; Ananthram Swami, Army Lab
Diversified Temporal Subgraph Pattern Mining
Author(s): Yi Yang, Fudan University; Da Yan, CUHK; Huanhuan Wu, CUHK; James Cheng*, CUHK; Shuigeng Zhou, Fudan University; John C.S. Lui, The Chinese University of Hong Kong
Ranking Causal Anomalies via Temporal and Dynamical Analysis on Vanishing Correlations
Author(s): Wei Cheng*, NEC Labs America; Kai Zhang, NEC labs America; Haifeng Chen, NEC Research Lab; Guofei Jiang, NEC labs America; Wei Wang, UC Los Angeles
Compressing Graphs and Indexes with Recursive Graph Bisection
Author(s): Laxman Dhulipala, Carnegie Mellon University; Igor Kabiljo, Facebook; Brian Karrer, Facebook; Giuseppe Ottaviano, Facebook; Sergey Pupyrev*, Facebook; Alon Shalita, Facebook
Positive-Unlabeled Learning in Streaming Networks
Author(s): Shiyu Chang*, UIUC; Yang Zhang, UIUC; Jiliang Tang, Yahoo Labs; Dawei Yin, ; Yi Chang, Yahoo! Labs; Mark Hasegawa-Johnson, UIUC; Thomas Huang, UIUC
FRAUDAR: Bounding Graph Fraud in the Face of Camouflage
Author(s): Bryan Hooi*, Carnegie Mellon University; Hyun Ah Song, Carnegie Mellon University; Alex Beutel, Carnegie Mellon University; Neil Shah, Carnegie Mellon University; Kijung Shin, Carnegie Mellon University; Christos Faloutsos, Carnegie Mellon University
Inferring Network Effects from Observational Data
Author(s): David Arbour*, University of Massachusetts Am; Dan Garant, University of Massachusetts Amherst; David Jensen, UMass Amherst
TRIEST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
Author(s): Lorenzo De Stefani*, Brown University; Alessandro Epasto, Brown; Matteo Riondato, Two Sigma Investments; Eli Upfal, Brown University