AGWAN: A Generative Model for Labelled, Weighted Graphs

Michael Davis, Weiru Liu, Paul Miller

Research output: Contribution to conferencePaper

334 Downloads (Pure)

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 present AGWAN (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 AGWAN model to real-world graphs and for generating random graphs from the model. Using the Enron “who communicates with whom” social graph, 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 the structure of real-world graphs.
Original languageEnglish
Number of pages12
Publication statusPublished - 27 Sept 2013
EventSecond International Workshop on New Frontiers in Mining Complex Patterns - Prague, Czech Republic
Duration: 23 Sept 201327 Sept 2013

Conference

ConferenceSecond International Workshop on New Frontiers in Mining Complex Patterns
Country/TerritoryCzech Republic
CityPrague
Period23/09/201327/09/2013

Fingerprint

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

Cite this