Regular Decomposition of Large Graphs: Foundation of a Sampling Approach to Stochastic Block Model Fitting

Show simple item record

dc.contributor.author Reittu, Hannu
dc.contributor.author Norros, Ilkka
dc.contributor.author Räty, Tomi
dc.contributor.author Bolla, Marianna
dc.contributor.author Bazsó, Fülöp
dc.date.accessioned 2019-03-10T04:22:33Z
dc.date.available 2019-03-10T04:22:33Z
dc.date.issued 2019-03-07
dc.identifier.uri http://hdl.handle.net/10138/300008
dc.description.abstract Abstract We analyze the performance of regular decomposition, a method for compression of large and dense graphs. This method is inspired by Szemerédi’s regularity lemma (SRL), a generic structural result of large and dense graphs. In our method, stochastic block model (SBM) is used as a model in maximum likelihood fitting to find a regular structure similar to the one predicted by SRL. Another ingredient of our method is Rissanen’s minimum description length principle (MDL). We consider scaling of algorithms to extremely large size of graphs by sampling a small subgraph. We continue our previous work on the subject by proving some experimentally found claims. Our theoretical setting does not assume that the graph is generated from a SBM. The task is to find a SBM that is optimal for modeling the given graph in the sense of MDL. This assumption matches with real-life situations when no random generative model is appropriate. Our aim is to show that regular decomposition is a viable and robust method for large graphs emerging, say, in Big Data area.
dc.publisher Springer Berlin Heidelberg
dc.subject Community detection
dc.subject Sampling
dc.subject Consistency
dc.subject Martingales
dc.title Regular Decomposition of Large Graphs: Foundation of a Sampling Approach to Stochastic Block Model Fitting
dc.date.updated 2019-03-10T04:22:33Z
dc.language.rfc3066 en
dc.rights.holder The Author(s)
dc.type.uri http://purl.org/eprint/entityType/ScholarlyWork
dc.type.uri http://purl.org/eprint/entityType/Expression
dc.type.uri http://purl.org/eprint/type/JournalArticle

Files in this item

Total number of downloads: Loading...

Files Size Format View
41019_2019_Article_84.pdf 3.290Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record