Community Detection in Networks using Graph Distance
The study of networks has received increased attention recently not only from the social sciences and statistics but also from physicists, computer scientists and mathematicians. One of the principal problem in networks is community detection. Many algorithms have been proposed for community finding but most of them do not have have theoretical guarantee for sparse networks and networks close to the phase transition boundary proposed by physicists. There are some exceptions but all have some incomplete theoretical basis. Here we propose an algorithm based on the graph distance of vertices in the network. We give theoretical guarantees that our method works in identifying communities for block models and can be extended for degree-corrected block models and block models with the number of communities growing with number of vertices. Despite favorable simulation results, we are not yet able to conclude that our method is satisfactory for worst possible case. We illustrate on a network of political blogs, Facebook networks and some other networks.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery
We study community detection in multiple networks whose nodes and edges are jointly correlated. This setting arises naturally in applications such as social platforms, where a shared set of users may exhibit both correla…
AttributeCommunity DetectionGraph MatchingStochastic Block ModelGraph Vertex Embeddings: Distance, Regularization and Community Detection
Graph embeddings have emerged as a powerful tool for representing complex network structures in a low-dimensional space, enabling the use of efficient methods that employ the metric structure in the embedding space as a …
Community DetectionSparsity-aware Robust Community Detection(SPARCODE)
Community detection refers to finding densely connected groups of nodes in graphs. In important applications, such as cluster analysis and network modelling, the graph is sparse but outliers and heavy-tailed noise may ob…
Community DetectionRevisiting FastMap: New Applications
FastMap was first introduced in the Data Mining community for generating Euclidean embeddings of complex objects. In this dissertation, we first present FastMap to generate Euclidean embeddings of graphs in near-linear t…
Community DetectionCommunity detection with spiking neural networks for neuromorphic hardware
We present results related to the performance of an algorithm for community detection which incorporates event-driven computation. We define a mapping which takes a graph G to a system of spiking neurons. Using a fully c…
Community Detection