Community detection in dynamic attributed networks

Abstract

The analysis of social networks can be helpful to support policy and decision-making processes. One of the tools to achieve this task is community detection. This approach allows the detection of groups, mostly on static networks where the links between nodes are available. Real-world problems, however, are often characterized by behavior that changes over time. We need dynamic community detection algorithms in such cases because they better capture the underlying dynamics. A step further in this sense is to include attribute information about the nodes and detect groups on dynamic networks that evolve to obtain more accurate results. Also, being able to detect overlapping communities offers an improvement since nodes can belong to different groups at the same time. Furthermore, the capability of an approach to automatically detect the number of groups is also relevant. This thesis presents two models for community detection in dynamic attributed networks.

The first model, for COmmunity DEtection in Dynamic Attributed NETworks (CoDeDANet), comprises two phases. In the first phase, based on spectral clustering, the attributes' importance is optimized in a setting that joins the nodes' features with a topological structure. In the second phase, tensors are used to consider current and past information. This algorithm detects disjoint groups, and the number of communities is a parameter of the approach.

The second model, for Overlapping COmmunity DEtection in Dynamic Attributed NETworks (OCoDeDANet), uses non-negative matrix factorization in a probabilistic approach to detect disjoint and overlapping communities in an iterative algorithm that maximizes the model posterior given the observations. In this case, the algorithm itself determines the number of groups with an automatic relevance determination process.

Both approaches were tested on several synthetic and real-world networks. Results show that our models outperform state-of-the-art algorithms. The use of networks' evolution and nodes' attributes in our approaches led to more accurate communities.

The analysis of social networks can be helpful to support policy and decision-making processes. One of the tools to achieve this task is community detection. This approach allows the detection of groups, mostly on static networks where the links between nodes are available. Real-world problems, however, are often characterized by behavior that changes over time. We need dynamic community detection algorithms in such cases because they better capture the underlying dynamics. A step further in this sense is to include attribute information about the nodes and detect groups on dynamic networks that evolve to obtain more accurate results. Also, being able to detect overlapping communities o ers an improvement since nodes can belong to di erent groups at the same time. Furthermore, the capability of an approach to automatically detect the number of groups is also relevant. This thesis presents two models for community detection in dynamic attributed networks. The rst model, for COmmunity DEtection in Dynamic Attributed NETworks (CoDeDANet), comprises two phases. In the rst phase, based on spectral clustering, the attributes' importance is optimized in a setting that joins the nodes' features with a topological structure. In the second phase, tensors are used to consider current and past information. This algorithm detects disjoint groups, and the number of communities is a parameter of the approach. The second model, for Overlapping COmmunity DEtection in Dynamic Attributed NETworks (OCoDeDANet), uses non-negative matrix factorization in a probabilistic approach to detect disjoint and overlapping communities in an iterative algorithm that maximizes the model posterior given the observations. In this case, the algorithm itself determines the number of groups with an automatic relevance determination process. Both approaches were tested on several synthetic and real-world networks. Results show that our models outperform state-of-the-art algorithms. The use of networks' evolution and nodes' attributes in our approaches led to more accurate communities.