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
Random Multigraphs: Complexity Measures, Probability Models and Statistical Inference
Stockholm University, Faculty of Social Sciences, Department of Statistics.
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 [en]
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: urn:nbn:se:su:diva-82697ISBN: 978-91-7447-610-1 (print)OAI: oai:DiVA.org:su-82697DiVA: diva2:571343
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
List of papers
1. Complexity of Families of Multigraphs
Open this publication in new window or tab >>Complexity of Families of Multigraphs
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
network analysis, edge multiplicity, complexity measure, entropy, labeled graph, isomorphism
National Category
Probability Theory and Statistics
Research subject
Statistics
Identifiers
urn:nbn:se:su:diva-82689 (URN)9780983937524 (ISBN)
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
2. Random Stub Matching Models of Multigraphs
Open this publication in new window or tab >>Random Stub Matching Models of Multigraphs
(English)Manuscript (preprint) (Other academic)
National Category
Social Sciences
Research subject
Statistics
Identifiers
urn:nbn:se:su:diva-82691 (URN)
Note

Utgiven som Research Report 2012:1, Statistiska institutionen, Stockholms universitet

Available from: 2012-11-22 Created: 2012-11-22 Last updated: 2012-12-20Bibliographically approved
3. Statistical Analysis of Multigraphs
Open this publication in new window or tab >>Statistical Analysis of Multigraphs
(English)Manuscript (preprint) (Other academic)
National Category
Social Sciences
Research subject
Statistics
Identifiers
urn:nbn:se:su:diva-82692 (URN)
Note

Utgiven som Research Report 2012:2, Statistiska institutionen, Stockholms universitet

Available from: 2012-11-22 Created: 2012-11-22 Last updated: 2012-12-20Bibliographically approved
4. Some Multigraph Algorithms
Open this publication in new window or tab >>Some Multigraph Algorithms
(English)Manuscript (preprint) (Other academic)
National Category
Social Sciences
Research subject
Statistics
Identifiers
urn:nbn:se:su:diva-82693 (URN)
Note

Utgiven som Research Report 2012:3, Statistiska institutionen, Stockholms universitet

Available from: 2012-11-22 Created: 2012-11-22 Last updated: 2012-12-20Bibliographically approved

Open Access in DiVA

fulltext(122 kB)641 downloads
File information
File name FULLTEXT01.pdfFile size 122 kBChecksum SHA-512
e7e6b4d1ada250f22187eaa0c838b51f8c5cc2ef1fdde79e9a21fce1ecf640fa9e725e1fb975bed6bc0bf9cff5e28195936b24fcda2f27ff44eaafe665b4ded9
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Shafie, Termeh
By organisation
Department of Statistics
Social Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 641 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1024 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