Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.


Share this Page URL
Help

INTRODUCTION > INTRODUCTION - Pg. 89

Data Mining Techniques for Communities' Detection in Dynamic Social Networks INTRODUCTION Social network analysis conceives social relation- ships in terms of graphs of interactions whose nodes represent individual actors within the net- works and links social interactions such as ideas, friendship, collaboration, trade, etc. Virtual com- munities, and particularly online communities, are peculiar social networks whose analysis is facilitated by the fact that the network is in some sense monitored continuously. Social networks have attracted a large amount of attention from epidemiologists, sociologists, biologists and com- puter scientists that have shown the ubiquitous role played by social networks in determining the way problems are solved or organizations are run. The study of such networks has attracted much atten- tion in the recent years and has proceeded along two main tracks: the analysis of graph properties, such as degree distribution, diameter or simple to crossing between clusters), minus the expected number of such edges if the graph was random conditioned on its degree distribution. Commu- nity structures often maximize the modularity measure. However, this measure has an intrinsic resolution scale, and can therefore fail to detect communities smaller than that scale and favor in general communities of similar size (Fortunato et al., 2007). Moreover, it has been shown (Brandes et al., 2008) that finding the community structure of maximum modularity for a given graph is NP- complete and thus heuristics have been proposed that approximate this optimization problem. Instead of directly looking for a global structure of the graph, such as a partition of the vertices, it can be more efficient to proceed in two steps. One might first compute subgraphs that capture locally strong associations between vertices and then use these local patterns to construct a global model of the graph's dynamics. Such a frame-