Cognitive Community Detection
|A Cognitive Approach to the Community Detection Problem|
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 representative 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 return 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 directly connecting to a “central node”. Both 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.
|A Cognitive Heuristic model for Local Community Recognition|
The Self Awareness topic represents one of the most attractive and fascinating attribute of the Human Cognition. The understanding of its key features will have presumably a relevant impact on the design of the future self-aware ICT application, and the forecasting of the systems dominated by self-aware entities. The modelling of these concepts would have a large impact on the knowledge of social systems, ranging from the small group and the micro trading dynamics to the modelling of cultural evolution and of societies. In the case study we first introduce a new theoretical framework to modelling the probabilistic reasoning and the Cognitive Heuristics at a computational level, and some already developed functions within the framework. Then, two relevant examples of application will be faced: the ”Local Community Detection problem” and the ”Epidemics Forecasting problem”.
We presented here only preliminary investigations, a more detailed investigation on the statistical properties of the algorithms is underway. Primate communities are strongly social, and therefore we have developed sophisticated tools for detecting the various degree of relationship. These tools are quite slow, since in primate a large part of time is devoted to exploration and communication, and require large computational efforts and large brains. There is not a unique definition of a community, so an exploratory algorithm, like the one that humans have presumably developed during their evolution, should present different clustering for different values of the parameters, or for different iterations. We investigated two methods, one based on pure information propagation and the other based on rewiring. The nonlinear part of these method, responsible for the actual elaboration of information, is inspired to a chemical/ecological competition model. The results that we obtained are promising.
The method under investigation is not competitive with respect to others, but it provides a natural “scanning” of the various clustering levels. Moreover, our method can be naturally applied to weighted graphs
| Modeling Epidemic Risk Perception in Networks with Community Structure |
We study the influence of global, local and community-level risk perception on the extinction probability of a disease in several mod- els of social networks. In particular, we study the infection progression as a susceptible-infected-susceptible (SIS) model on several modular net- works, formed by a certain number of random and scale-free communi- ties. We find that in the scale-free networks the progression is faster than in random ones with the same average connectivity degree. For what concerns the role of perception, we find that the knowledge of the infection level in one’s own neighborhood is the most effective property in stopping the spreading of a disease, but at the same time the more expensive one in terms of the quantity of required information, thus the cost/effectiveness optimum is a tradeoff between several parameters.