On Finding the Community with Maximum Persistence Probability

Alessandro Avellone, Stefano Benati, Rosanna Grassi and Giorgio Rizzini

Papers from arXiv.org

Abstract: The persistence probability is a statistical index that has been proposed to detect one or more communities embedded in a network. Even though its definition is straightforward, e.g, the probability that a random walker remains in a group of nodes, it has been seldom applied possibly for the difficulty of developing an efficient algorithm to calculate it. Here, we propose a new mathematical programming model to find the community with the largest persistence probability. The model is integer fractional programming, but it can be reduced to mixed-integer linear programming with an appropriate variable substitution. Nevertheless, the problem can be solved in a reasonable time for networks of small size only, therefore we developed some heuristic procedures to approximate the optimal solution. First, we elaborated a randomized greedy-ascent method, taking advantage of a peculiar data structure to generate feasible solutions fast. After analyzing the greedy output and determining where the optimal solution is eventually located, we implemented improving procedures based on a local exchange, but applying different long term diversification principles, that are based on variable neighborhood search and random restart. Next, we applied the algorithms on simulated graphs that reproduce accurately the clustering characteristics found in real networks to determine the reliability and the effectiveness of our methodology. Finally, we applied our method to two real networks, comparing our findings to what found by two well-known alternative community detection procedures.

Date: 2022-06
New Economics Papers: this item is included in nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 4OR-Q J Oper Res (2023)

Downloads: (external link)
http://arxiv.org/pdf/2206.10330 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2206.10330

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().