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

Fingerprint

Generative Models
Weighted Graph
Graph in graph theory
Numerics
Labels
Attribute
Random Graphs
Heavy-tailed Distribution
Property of set
Degree Distribution
Undirected Graph
Model
Directed Graph
Clustering
Generator
Tend
Arbitrary
Vertex of a graph

Keywords

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

Cite this

Davis, M., Liu, W., Miller, P., Hunter, R. F., & Kee, F. (2014). AGWAN: A Generative Model for Labelled, Weighted Graphs. In New 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 (Vol. 8399 LNAI, pp. 181-200). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8399 LNAI). Springer-Verlag.
Davis, Michael ; Liu, Weiru ; Miller, Paul ; Hunter, Ruth F. ; Kee, Frank. / AGWAN: A Generative Model for Labelled, Weighted Graphs. New 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. Vol. 8399 LNAI Springer-Verlag, 2014. pp. 181-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inbook{484d27fe7c39493185f676418b561eb4,
title = "AGWAN: A Generative Model for Labelled, Weighted Graphs",
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.",
keywords = "Graph generators, Graph mining, Labelled graphs, Network models, Random graphs, Weighted graphs",
author = "Michael Davis and Weiru Liu and Paul Miller and Hunter, {Ruth F.} and Frank Kee",
year = "2014",
month = "1",
day = "1",
language = "English",
isbn = "9783319084060",
volume = "8399 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "181--200",
booktitle = "New 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",

}

Davis, M, Liu, W, Miller, P, Hunter, RF & Kee, F 2014, AGWAN: A Generative Model for Labelled, Weighted Graphs. in New 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. vol. 8399 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8399 LNAI, Springer-Verlag, pp. 181-200, 2nd 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, 27/09/2013.

AGWAN: A Generative Model for Labelled, Weighted Graphs. / Davis, Michael; Liu, Weiru; Miller, Paul; Hunter, Ruth F.; Kee, Frank.

New 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. Vol. 8399 LNAI Springer-Verlag, 2014. p. 181-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8399 LNAI).

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

TY - CHAP

T1 - AGWAN: A Generative Model for Labelled, Weighted Graphs

AU - Davis, Michael

AU - Liu, Weiru

AU - Miller, Paul

AU - Hunter, Ruth F.

AU - Kee, Frank

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Graph generators

KW - Graph mining

KW - Labelled graphs

KW - Network models

KW - Random graphs

KW - Weighted graphs

M3 - Chapter (peer-reviewed)

AN - SCOPUS:84905264174

SN - 9783319084060

VL - 8399 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 181

EP - 200

BT - New 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

PB - Springer-Verlag

ER -

Davis M, Liu W, Miller P, Hunter RF, Kee F. AGWAN: A Generative Model for Labelled, Weighted Graphs. In New 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. Vol. 8399 LNAI. Springer-Verlag. 2014. p. 181-200. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).