NeSiFC: Neighbors’ Similarity-Based Fuzzy Community Detection Using Modified Local Random Walk

This article proposes a neighbors' similarity-based fuzzy community detection (FCD) method, which we call "NeSiFC." In the proposed NeSiFC approach, we compute the similarity between two neighbors by introducing a modified local random walk (mLRW). Basically, in a network, a node and its' neighbors with noticeable similarities among them construct a community. To measure this similarity, we introduce a new metric, called the peripheral similarity index (PSI). This PSI is used to construct the transition probability matrix for the mLRW. The mLRW is applied for each node until it meets a parameter called step coefficient. The mLRW gives better neighbors' similarity for community detection. Finally, a fuzzy membership function is used iteratively to compute the membership degrees for all nodes with reference to existing communities. The proposed NeSiFC has no dependence on the network characteristics, and no adjustment or fine tuning of more than one parameter is needed. To show the efficacy of the proposed NeSiFC approach, we provide a thorough comparative performance analysis considering a set of well-known FCD algorithms viz., the genetic algorithm for fuzzy community detection, membership degree propagation, center-based fuzzy graph clustering, FMM/H2, and FuzAg on a set of popular benchmarks, as well as real-world datasets. For both disjoint and overlapping community structures, results of various accuracy and quality metrics indicate the outstanding performance of our proposed NeSiFC approach. The asymptotic complexity of the proposed NeSiFC is found as O(n2).