Cognitive Approach to Community Detection**Responsible: Andrea Guazzini, Emanuele Massaro**

Detecting communities is a task of great importance in many disciplines, namely sociology, biology and computer science, where systems are often represented as graphs. Community detection is linked to clustering of data: many clustering methods establish links among representa tive points that are nearer than a given threshold, and then proceed in identifying communities on the resulting graphs. Given a graph, a community is a group of vertices “more linked” than between the group and the rest of the graph. This is clearly a lousy definition, and indeed, or a connected graph, there is not a clear distinction between a community and a rest of the graph. In general, there is a continuum of nested communities whose boundaries are somewhat arbitrary: the structure of communities can be seen as a hierarchical dendogram. A community-detection algorithm should therefore retu

rn different “views”, according to the value of some control parameter. Due to the arbitrariness of the definition, such “views” are relevant if they are not crucially dependent on the precise value of the parameters, i.e., if communities appears as “plateaus” when varying the control parameter.

We want to explore the behavior of exploratory methods inspired to human heuristics, in the hope of exploiting the “social knowledge” of human mind and also for developing more “natural” human-computer interfaces. Clearly, we do not pretend to simulate the real human behavior, but only to study the behavior of simplified models inspired to it. In particular, we deal with the task of identifying communities in an existing graphs, using a local algorithm and not relying on global quantities like betweenness, centrality, etc. An individual is simply modeled as a memory and a set of connections to other individuals. We explore two different approaches: in the first, information about neighboring nodes if propagated and elaborated locally, but the connections do not change. In the second approach, information is not elaborated while it is the wiring that is varied with the result of direct ly connecting to a “central node”. B

oth processes can be considered implementations of the availability heiristic, which is simply the assumption that the most vivid or easily recallable information give an accurate estimate of the frequency of the related event in the population.

In both approaches, the “learning” (nonlinear) phase is modeled after competition in chemical/ecological world. This can be considered an implementation of the anchoring heuristics, in which the judgment or the action is dominated by one or very few pieces of information, the most relevant ones.