Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity of Families of Multigraphs
Stockholm University, Faculty of Social Sciences, Department of Statistics.
Stockholm University, Faculty of Social Sciences, Department of Statistics.
2012 (English)In: 2012 JSM Proceedings: Papers Presented at the Joint Statistical Meetings, San Diego, California, July 28-August 2, 2012, and Other ASA-sponsored Conferences, American Statistical Association , 2012Conference paper, Published paper (Refereed)
Abstract [en]

This article describes families of finite multigraphs with labeled or unlabeled edges and vertices. It shows how size and complexity vary for different types of equivalence classes of graphs defined by ignoring only edge labels or ignoring both edge and vertex labels. Complexity is quantified by the distribution of edge multiplicities, and different complexity measures are discussed. Basic occupancy models for multigraphs are used to illustrate different graph distributions on isomorphism and complexity. The loss of information caused by ignoring edge and vertex labels is quantified by entropy and joint information that provide tools for studying properties of and relations between different graph families.

Place, publisher, year, edition, pages
American Statistical Association , 2012.
Keyword [en]
network analysis, edge multiplicity, complexity measure, entropy, labeled graph, isomorphism
National Category
Probability Theory and Statistics
Research subject
Statistics
Identifiers
URN: urn:nbn:se:su:diva-82689ISBN: 9780983937524 (print)OAI: oai:DiVA.org:su-82689DiVA: diva2:571312
Conference
Joint Statistical Meetings, San Diego, California, July 28-August 2, 2012
Available from: 2012-11-22 Created: 2012-11-22 Last updated: 2017-11-16Bibliographically approved
In thesis
1. Random Multigraphs: Complexity Measures, Probability Models and Statistical Inference
Open this publication in new window or tab >>Random Multigraphs: Complexity Measures, Probability Models and Statistical Inference
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis is concerned with multigraphs and their complexity which is defined and quantified by the distribution of edge multiplicities. Two random multigraph models are considered.  The first model is random stub matching (RSM) where the edges are formed by randomly coupling pairs of stubs according to a fixed stub multiplicity sequence. The second model is obtained by independent edge assignments (IEA) according to a common probability distribution over the edge sites. Two different methods for obtaining an approximate IEA model from an RSM model are also presented.

In Paper I, multigraphs are analyzed with respect to structure and complexity by using entropy and joint information. The main results include formulae for numbers of graphs of different kinds and their complexity. The local and global structure of multigraphs under RSM are analyzed in Paper II. The distribution of multigraphs under RSM is shown to depend on a single complexity statistic. The distributions under RSM and IEA are used for calculations of moments and entropies, and for comparisons by information divergence. The main results include new formulae for local edge probabilities and probability approximation for simplicity of an RSM multigraph. In Paper III, statistical tests of a simple or composite IEA hypothesis are performed using goodness-of-fit measures. The results indicate that even for very small number of edges, the null distributions of the test statistics under IEA have distributions that are  well approximated by their asymptotic χ2-distributions. Paper IV contains the multigraph algorithms that are used for numerical calculations in Papers I-III.

Place, publisher, year, edition, pages
Stockholm: Department of Statistics, Stockholm University, 2012. 9 p.
Keyword
multigraph, vertex labeled graph, edge labeled graph, isomorphism, edge multiplicity, simplicity and complexity, entropy, joint information, information divergence, goodness-of-fit
National Category
Social Sciences
Research subject
Statistics
Identifiers
urn:nbn:se:su:diva-82697 (URN)978-91-7447-610-1 (ISBN)
Public defence
2013-01-10, hörsal 5, hus B, Universitetsvägen 10 B, Stockholm, 13:00 (English)
Opponent
Supervisors
Available from: 2012-12-20 Created: 2012-11-22 Last updated: 2012-12-20Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Shafie, TermehFrank, Ove
By organisation
Department of Statistics
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 240 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf