Abstract
In this paper, we focus on the problem of community detection on TSina: the most popular microblogging network in China. By characterizing the structure and content of microgroup (community) on TSina in detail, we reveal that different from ordinary social networks, the degree assortativity coefficients are negative on most microgroups. In addition, we find that users from the same microgroup likely exhibit some similar attributes (e.g., sharing many followers, tags and topics). Inspired by these new findings, we propose a united method for microgroup detection without losing the information of link structure and user attribute. First, the link direction is converted to the weight by giving higher value to the more surprising link, while attribute similarity between two users is measured by the Jaccard coefficient of common features like followers, tags, and topics. Then, above two factors are uniformly converted to the edge weight of a newly generated network. Finally, many frequently used community detection algorithms that support weighted network would be employed. Extensive experiments on real social networks show that the factors of link structure and user attribute play almost equally important roles in microgroup detection on TSina. Our newly proposed method significantly outperforms the traditional methods with average accuracy being improved by 25%, and the number of unrecognized users decreasing by about 75%.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fortunato, S.: Community detection in graphs. Physics Reports 486(3-5), 75–174 (2010)
Danon, L., Duch, J., Arenas, A., Daz-guilera, A.: Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 9008, 09008 (2005)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. PNAS 99(12), 7821–7826 (2002)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. EÂ 69(2), 26113 (2004)
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proceedings of the National Academy of Sciences 101(9), 2658 (2004)
Palla, G., Derenyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814 (2005)
Arenas, A., DÃaz-Guilera, A., Pérez-Vicente, C.J.: Synchronization reveals topological scales in complex networks. Phys. Rev. Lett. 96(11), 114102 (2006)
Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. EÂ 70(6), 66111 (2004)
Flake, G., Lawrence, S., Giles, C., Coetzee, F.: Self-organization and identification of Web communities. Computer 35(3), 66–70 (2002)
Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430–452 (1990)
Kernighan, B.W., Lin, S.: An Efficient Heuristic Procedure for Partitioning Graphs. The Bell system technical journal 49(1), 291–307 (1970)
Gregory, S.: Finding overlapping communities in networks by label propagation. New Journal of Physics 12(10), 103018+ (2010)
Stanoev, A., Smilkov, D., Kocarev, L.: Identifying communities by influence dynamics in social networks (April 2011)
Yang, T., Chi, Y., Zhu, S., Gong, Y., Jin, R.: Directed network community detection: A popularity and productivity link model. In: SIAM International Conference on Data Mining, pp. 742–753 (2010)
Cohn, D., Hofmann, T.: The missing link - a probabilistic model of document content and hypertext connectivity. In: Neural Information Processing Systems, vol. 13 (2001)
Getoor, L., Friedman, N., Koller, D., Taskar, B.: Learning probabilistic models of link structure. Journal of Machine Learning Research 3, 679–707 (2002)
Stephen, E.E., Fienberg, S., Lafferty, J.: Mixed membership models of scientific publications. Proceedings of the National Academy of Sciences (2004)
Yang, T., Jin, R., Chi, Y., Zhu, S.: Combining link and content for community detection: a discriminative approach. In: Knowledge Discovery and Data Mining, pp. 927–936 (2009)
Dietz, L., Bickel, S., Scheffer, T.: Unsupervised prediction of citation influences. In: Proceedings of the 24th International Conference on Machine Learning, pp. 233–240 (2007)
Amit Gruber, M.R.Z., Weiss, Y.: Latent topic models for hypertext. In: Uncertainty in Artificial Intelligence, pp. 230–239 (2008)
Cha, M., Mislove, A., Gummadi, P.K.: A measurement-driven analysis of information propagation in the flickr social network. World Wide Web Conference Series, pp. 721–730 (2009)
Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social networks. In: Knowledge Discovery and Data Mining, pp. 611–617 (2006)
Kwak, H., Lee, C., Park, H., Moon, S.B.: What is twitter, a social network or a news media? World Wide Web Conference Series, pp. 591–600 (2010)
Newman, M.E.J.: Mixing patterns in networks. Phys. Rev. EÂ 67(2), 26126 (2003)
Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 1019–1031 (2007)
Kim, Y., Son, S.-W., Jeong, H.: Community Identification in Directed Networks. In: Zhou, J. (ed.) Complex 2009. LNICST, vol. 5, pp. 2050–2053. Springer, Heidelberg (2009)
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. PNASÂ 105, 1118 (2008)
Lancichinetti, A., Radicchi, F., Ramasco, J.J.: Statistical significance of communities in networks. Phys. Rev. EÂ 81(4), 46110 (2010)
Zachary, W.: An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33, 452–473 (1977)
Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54(4), 396–405 (2003)
Traud, A.L., Kelsic, E.D., Mucha, P.J., Porter, M.A.: Comparing Community Structure to Characteristics in Online Collegiate Social Networks. In: Proceedings of the 2009 APS March Meeting (March 2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xiong, X., Niu, X., Zhou, G., Xu, K., Huang, Y. (2011). Microgroup Mining on TSina via Network Structure and User Attribute. In: Tang, J., King, I., Chen, L., Wang, J. (eds) Advanced Data Mining and Applications. ADMA 2011. Lecture Notes in Computer Science(), vol 7121. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25856-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-25856-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25855-8
Online ISBN: 978-3-642-25856-5
eBook Packages: Computer ScienceComputer Science (R0)