Community Recovery in a Preferential Attachment Graph

DOI10.1109/TIT.2019.2927624zbMATH Open1433.94160arXiv1801.06818OpenAlexW2962843630WikidataQ127491886 ScholiaQ127491886MaRDI QIDQ5211481FDOQ5211481

Authors: Bruce Hajek, Suryanarayana Sankagiri 

Publication date: 28 January 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: A message passing algorithm is derived for recovering communities within a graph generated by a variation of the Barab'{a}si-Albert preferential attachment model. The estimator is assumed to know the arrival times, or order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Comparison of the performance of the algorithms shows it is beneficial to know the arrival times, not just the number, of the children. The probability of correct classification of a vertex is asymptotically determined by the fraction of vertices arriving before it. Two extensions of Algorithm C are given: the first is based on joint likelihood of the children of a fixed set of vertices; it can sometimes be used to seed the message passing algorithm. The second is the message passing algorithm. Simulation results are given.

Full work available at URL: https://arxiv.org/abs/1801.06818

Recommendations

• Community Recovery in Hypergraphs
• Direction recovery in undirected social networks based on community structure and popularity
• scientific article; zbMATH DE number 5621258
• Community detection with dependent connectivity
• Preferential attachment in randomly grown networks
• COMMUNITY FINDING IN COMPLEX NETWORKS
• Growing random graphs with a preferential attachment structure

zbMATH Keywords

message passing algorithmgraph generated by variation of Barabási-Albert preferential attachment modelrecovering communities

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

Cited In (4)

• Random networks with heterogeneous reciprocity
• Inference in balanced community modulated recursive trees
• Putting down roots: a graphical exploration of community attachment
• A new preferential model with homophily for recommender systems

This page was built for publication: Community Recovery in a Preferential Attachment Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211481)