AGWAN: A Generative Model for Labelled, Weighted Graphs

Michael Davis*, Weiru Liu, Paul Miller, Ruth F. Hunter, Frank Kee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

3 Citations (Scopus)

Abstract

Real-world graphs or networks tend to exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Much effort has been directed into creating realistic and tractable models for unlabelled graphs, which has yielded insights into graph structure and evolution. Recently, attention has moved to creating models for labelled graphs: many real-world graphs are labelled with both discrete and numeric attributes. In this paper, we presentAgwan (Attribute Graphs: Weighted and Numeric), a generative model for random graphs with discrete labels and weighted edges. The model is easily generalised to edges labelled with an arbitrary number of numeric attributes. We include algorithms for fitting the parameters of the Agwanmodel to real-world graphs and for generating random graphs from the model. Using real-world directed and undirected graphs as input, we compare our approach to state-of-the-art random labelled graph generators and draw conclusions about the contribution of discrete vertex labels and edge weights to graph structure.
Original languageEnglish
Title of host publicationNew Frontiers in Mining Complex Patterns: Second International Workshop, NFMCP 2013, Held in Conjunction with ECML/PKDD 2013, Prague, Czech Republic, September 27, 2013: Revised Selected Papers
PublisherSpringer-Verlag
Pages181-200
Number of pages20
Volume8399 LNAI
ISBN (Print)9783319084060
Publication statusPublished - 01 Jan 2014
Event2nd International Workshop on New Frontiers in Mining Complex Patterns, NFMCP 2013, in Conjunction with the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2013 - Prague, Czech Republic
Duration: 27 Sep 201327 Sep 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8399 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference2nd International Workshop on New Frontiers in Mining Complex Patterns, NFMCP 2013, in Conjunction with the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2013
CountryCzech Republic
CityPrague
Period27/09/201327/09/2013

Keywords

  • Graph generators
  • Graph mining
  • Labelled graphs
  • Network models
  • Random graphs
  • Weighted graphs

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'AGWAN: A Generative Model for Labelled, Weighted Graphs'. Together they form a unique fingerprint.

Cite this