MetaGraphs

Find and extract subgraphs in a single massive graph

Input File Format

• http://gephi.github.io/users/supported-graph-formats/gdf-format/

Notes

• String mapped to a hash key: int(hashlib.sha1(s).hexdigest(), 16) % (10 ** 8) http://stackoverflow.com/questions/1303021/shortest-hash-in-python-to-name-cache-files http://stackoverflow.com/questions/16008670/python-how-to-hash-a-string-into-8-digits

Software

• Subgraph mining: But there are problems getting R 3 working with this package. http://stackoverflow.com/questions/19830394/error-with-setwd-in-r Resources:

  • https://www.researchgate.net/post/Have_anyone_implemented_gSpan_algorithm_in_c_R_or_Matlab_for_frequent_sub-graph_mining
  • In R, install igraph and then the subgraph mining package
  • http://www.csc.ncsu.edu/faculty/samatova/practical-graph-mining-with-R/PracticalGraphMiningWithR.html#SampleChapters

• gSPAN/gboost http://www.nowozin.net/sebastian/gboost/ gSpan: Frequent Subgraph Miner, University of Illinois at Urbana-Champaign

• Gaston

• spidermine

• closegraph

• Subdue

• GraphChi

  • http://datasciencelondon.org/tag/graphchi/

• Grami

• GBAD: Graph-Based Anomaly Detection, Tennessee Technological University

• FSG: Frequent Subgraph Miner (part of the PAFI system), University of Minnesota

• METIS: Graph Partitioner, University of Minnesota

• Fast Frequent Subgraph Mining (FFSM) alpha Brought to you by: stoicboy

Data-sets

• Twitter (socialcomputing.asu.edu/datasets/Twitter).
• ClueWeb graph (428M nodes, 1.5B edges).
• We make use of the WebFountain crawl, which contains over 2B pages and 50M sites.

References

Graph Data Mining - CS 790g Seminar: Complex Networks Department of Computer Science & Engineering UNR, Fall 2010

• www.cse.unr.edu/~mgunes/cs765/cs790f10/Lect12_GraphMining.ppt
• http://www.cse.unr.edu/~mgunes/cs765/cs790f10/

A Survey of Frequent Subgraph Mining Algorithms Chuntao Jiang, Frans Coenen and Michele Zito

• http://cgi.csc.liv.ac.uk/~frans/PostScriptFiles/ker-jct-6-May-11.pdf

NScale: Neighborhood-centric Large-Scale Graph Analytics in the Cloud Abdul Quamar University of Maryland abdul@cs.umd.edu Amol Deshpande University of Maryland amol@cs.umd.edu Jimmy Lin University of Maryland jimmylin@umd.edu Nov 2014

• http://arxiv.org/pdf/1405.1499v2.pdf
• http://wp.sigmod.org/?p=1497#reference

Frequent Subgraph Discovery in Large Attributed Streaming Graphs Abhik Ray Lawrence B. Holder abhik.ray@wsu.edu holder@wsu.edu Washington State University, School of EECS, Pullman, Washington 99164-2752 Sutanay Choudhury sutanay.choudhury@pnnl.gov Pacific Northwest National Laboratory, 902 Battelle Blvd, Richland, WA 99354

• http://ailab.wsu.edu/adgs/pdfs/RayBigMine2014.pdf

GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph Mohammed Elseidy Ecole Polytechnique Fe ́de ́rale de Lausanne mohammed.elseidy@epfl.ch https://github.com/ElSeidy/GraMi

• http://www.vldb.org/pvldb/vol7/p517-elseidy.pdf

Discovering Large Dense Subgraphs in Massive Graphs David Gibson Ravi Kumar Andrew Tomkins IBM Almaden Research Center, 2005

• http://www.vldb2005.org/program/paper/thu/p721-gibson.pdf

Finding Frequent Patterns in a Large Sparse Graph hsigram/vsigram glaros.dtc.umn.edu/.../fetch/.../sigramDMKD05.... University of Minnesota by M KURAMOCHI - 2005 - Cited by 308 - Nov 11, 2005 - and vertical pattern discovery paradigms, that find the connected subgraphs that have ...