تشخیص جامعه در شبکه های کارگردان و کاربرد آن در تحلیل شبکه های اجتماعی
Abstract: Community detection has been one of the central problems in network studies. Detecting communities in a directed network is particularly challenging due to the directionality in its links. In this thesis, we show that incorporating the direction of links reveals new perspectives on communities regarding to two different roles, source and terminal, that a node may play in a community. A novel concept of a community in a directed network, called directional community, is proposed, and its relation to a connectivity in directed networks and a quality measure of a community are investigated. Intriguingly, directional communities appear to be closely related to a unique spectral property of the graph Laplacian matrix and we exploit this connection using regularized SVD methods. We propose harvesting algorithms, coupled with the regularized SVDs, that are linearly scalable for efficient identification of directional communities in a massive directed network. In addition, we construct another class of algorithms that exploits the connectivity in directed networks and makes use of existing community detection algorithms intended for undirected networks. The proposed algorithms show remarkable performance and scalability on simulated benchmark networks and successfully recover communities in real network applications with more than millions of nodes. The actual running time of the algorithms for a network with a million links is less than an hour. The algorithms are applied to the task of analyzing community structures in massive social networks, which is of particular interest since a community in a social network reflects a group of users that demonstrates dense interactions within the group. Our proposed algorithms address two challenges in community detection in a large social network, 1) how to incorporate the directions of interactions, 2) how to search for communities in networks of millions of users. As an effort to obtain a social network with intrinsic community structures, the social interactions of sports fans, particularly of NCAA college football teams, are collected from a popular social media service, Twitter. The obtained social interaction network is a large directed network, which has about a half-million nodes and links. Proposed algorithms successfully identified the communities of the fans of each football team. In comparison to the existing community detection algorithms, our proposed methods successfully distinguish the two different roles of fans, celebrity types and supporters types.
Keywords: Pure sciences, Community extraction, Laplacian graph, Regularized SVD, Scalable algorithm, Social networks