Paper Info
Title
Exploiting Phase Transitions for the Efficient Sampling of the Fixed Degree Sequence Model.
Abstract
Real-world network data is often very noisy and contains erroneous or missing edges. These superfluous and missing edges can be identified statistically by assessing the number of common neighbors of the two incident nodes. To evaluate whether this number of common neighbors, the so called co-occurrence, is statistically significant, a comparison with the expected co-occurrence in a suitable random graph model is required. For networks with a skewed degree distribution, including most real-world networks, it is known that the fixed degree sequence model, which maintains the degrees of nodes, is favourable over using simplified graph models that are based on an independence assumption. However, the use of a fixed degree sequence model requires sampling from the space of all graphs with the given degree sequence and measuring the co-occurrence of each pair of nodes in each of the samples, since there is no known closed formula for this statistic. While there exist log-linear approaches such as Markov chain Monte Carlo sampling, the computational complexity still depends on the length of the Markov chain and the number of samples, which is significant in large-scale networks. In this article, we show based on ground truth data that there are various phase transition-like tipping points that enable us to choose a comparatively low number of samples and to reduce the length of the Markov chains without reducing the quality of the significance test. As a result, the computational effort can be reduced by an order of magnitudes.
Year
DOI
Venue
2015
10.1145/2808797.2809388
ASONAM
Keywords
Field
DocType
phase transition-like tipping points,fixed degree sequence model sampling,incident nodes,co-occurrence,random graph model,skewed degree distribution,real-world networks,node degree,independence assumption,log-linear approach,computational complexity,Markov chain
Slice sampling,Data mining,Markov chain mixing time,Markov chain Monte Carlo,Computer science,Markov model,Markov chain,Degree distribution,Variable-order Markov model,Artificial intelligence,Clustering coefficient,Machine learning
Conference
Citations 
PageRank 
References 
2
0.40
10
Authors
7
Name
Order
Citations
PageRank
Christian Brugger172.97
André Lucas Chinazzo220.74
Alexandre Flores John320.74
Christian De Schryver4568.84
Norbert Wehn51165137.17
Andreas Spitz6101.72
Katharina Anna Zweig78116.32