In this paper, we present the algorithm ComTector(Community DeTector) which is more efficient for the community detection in large-scale social networks based on the nature of overlapping communities in the real world. This algorithm does not require any priori knowledge about the number or the original division of the communities. Because real networks are often large sparse graphs, its running time is thus O(C × Tri2), where C is the number of the detected communities and Tri is the number of the triangles in the given network for the worst case. Then we propose a general naming method by combining the topological information with the entity attributes to define the discovered communities. With respected to practical applications, ComTector is challenged with several real life networks including the Zachary Karate Club, American College Football, Scientific Collaboration, and Telecommunications Call networks. Experimental results show that this algorithm can extract meaningful communities that are agreed with both of the objective facts and our intuitions.
ER - TY - CONF AU - Grahl, Miranda AU - Hotho, Andreas AU - Stumme, Gerd A2 - Hinneburg, Alexander T1 - Conceptual Clustering of Social Bookmark Sites T2 - Workshop Proceedings of Lernen - Wissensentdeckung - Adaptivität (LWA 2007) PB - Martin-Luther-Universität Halle-Wittenberg CY - PY - 2007/10 M2 - VL - IS - SP - 50 EP - 54 UR - http://www.tagora-project.eu/wp-content/2007/06/grahl_iknow07.pdf M3 - KW - clustering KW - community KW - detection L1 - SN - 978-3-86010-907-6 N1 - N1 - AB - ER - TY - CONF AU - Begelman, Grigory AU - Keller, Philipp AU - Smadja, Frank A2 - T1 - Automated Tag Clustering: Improving search and exploration in the tag space T2 - Proceedings of the WWW 2006 Workshop on Collaborative Web Tagging Workshop PB - CY - Edinburgh PY - 2006/05 M2 - VL - IS - SP - EP - UR - http://www.rawsugar.com/www2006/taggingworkshopschedule.html M3 - KW - clustering KW - community KW - detection L1 - http://www.rawsugar.com/www2006/20.pdf SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, MEJ T1 - Finding community structure in networks using the eigenvectors of matrices JO - Physical Review E PY - 2006/ VL - 74 IS - 3 SP - EP - UR - M3 - KW - community KW - detection KW - graph KW - modularity KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Schmitz, Patrick A2 - T1 - Inducing Ontology from Flickr Tags T2 - Proceedings of the Workshop on Collaborative Tagging at WWW2006 PB - CY - Edinburgh, Scotland PY - 2006/05 M2 - VL - IS - SP - EP - UR - http://.citeulike.org/user/ryanshaw/article/740688 M3 - KW - community KW - detection KW - learning KW - ontology L1 - schmitz06-inducing.pdf SN - N1 - N1 - AB - In this paper, we describe some promising initial results in inducing ontology from the Flickr tag vocabulary, using a subsumption-based model. We describe the utility of faceted ontology as a supplement to a tagging system and present our model and results. We propose a revised, probabilistic model using seed ontologies to induce faceted ontology, and describe how the model can integrate into the logistics of tagging communities. ER - TY - JOUR AU - Danon, L. AU - Diaz-Guilera, A. AU - Duch, J. AU - Arenas, A. T1 - Comparing community structure identification JO - Journal of Statistical Mechanics: Theory and Experiment PY - 2005/ VL - 9 IS - SP - EP - UR - M3 - KW - community KW - detection L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, M E AU - Girvan, M T1 - Finding and evaluating community structure in networks JO - Phys Rev E Stat Nonlin Soft Matter Phys PY - 2004/02 VL - 69 IS - 2 SP - 026113.1 EP - 15 UR - http://www.ncbi.nlm.nih.gov/pubmed/14995526 M3 - KW - detection KW - modularity KW - score L1 - SN - N1 - N1 - AB - We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems. ER - TY - JOUR AU - Newman, MEJ T1 - Detecting community structure in networks JO - The European Physical Journal B-Condensed Matter PY - 2004/ VL - 38 IS - 2 SP - 321 EP - 330 UR - M3 - KW - community KW - detection L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Huang, Xiaodi AU - Lai, Wei T1 - Identification of clusters in the Web graph based on link topology JO - Database Engineering and Applications Symposium, 2003. Proceedings. Seventh International PY - 2003/07 VL - IS - SP - 123 EP - 128 UR - M3 - KW - cluster KW - community KW - detection L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Flake, GW AU - Lawrence, S. AU - Giles, CL AU - Coetzee, FM T1 - Self-organization and identification of Web communities JO - Computer PY - 2002/ VL - 35 IS - 3 SP - 66 EP - 70 UR - M3 - KW - community KW - detection L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Dhillon, Inderjit S. A2 - T1 - Co-clustering documents and words using bipartite spectral graph partitioning T2 - KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining PB - ACM Press CY - New York, NY, USA PY - 2001/ M2 - VL - IS - SP - 269 EP - 274 UR - http://portal.acm.org/citation.cfm?id=502512.502550 M3 - 10.1145/502512.502550 KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - 158113391X N1 - N1 - AB - ER - TY - CONF AU - Wagstaff, Kiri AU - Cardie, Claire AU - Rogers, Seth AU - Schrödl, Stefan A2 - Brodley, Carla E. A2 - Danyluk, Andrea Pohoreckyj T1 - Constrained K-means Clustering with Background Knowledge. T2 - ICML PB - Morgan Kaufmann CY - PY - 2001/ M2 - VL - IS - SP - 577 EP - 584 UR - http://dblp.uni-trier.de/db/conf/icml/icml2001.html#WagstaffCRS01 M3 - KW - clustering KW - community KW - constrained KW - detection KW - k-means L1 - SN - 1-55860-778-1 N1 - N1 - AB - ER - TY - CONF AU - Flake, Gary William AU - Lawrence, Steve AU - Giles, C. Lee A2 - T1 - Efficient identification of Web communities T2 - KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining PB - ACM Press CY - New York, NY, USA PY - 2000/ M2 - VL - IS - SP - 150 EP - 160 UR - M3 - http://doi.acm.org/10.1145/347090.347121 KW - community KW - detection L1 - SN - 1-58113-233-6 N1 - N1 - AB - ER - TY - CONF AU - Shi, Jianbo AU - Malik, Jitendra A2 - T1 - Normalized Cuts and Image Segmentation. T2 - CVPR PB - CY - PY - 1997/ M2 - VL - IS - SP - 731 EP - 737 UR - http://dblp.uni-trier.de/db/conf/cvpr/cvpr1997.html#ShiM97 M3 - KW - clustering KW - community KW - detection KW - ncut L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Berry, M.W. AU - Dumais, S.T. AU - O'Brien, G.W. T1 - Using Linear Algebra for Intelligent Information Retrieval JO - SIAM REVIEW PY - 1995/ VL - 37 IS - SP - 573 EP - 595 UR - M3 - KW - algebra KW - community KW - detection KW - linear KW - svd KW - weka L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Chan, Pak K. AU - Schlag, Martine D. F. AU - Zien, Jason Y. T1 - Spectral K-way ratio-cut partitioning and clustering. JO - IEEE Trans. on CAD of Integrated Circuits and Systems PY - 1994/ VL - 13 IS - 9 SP - 1088 EP - 1096 UR - http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94 M3 - KW - community KW - detection KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Fiedler, M. T1 - Algebraic connectivity of graphs JO - Czechoslovak Mathematical Journal PY - 1973/ VL - 23 IS - 98 SP - 298 EP - 305 UR - M3 - KW - community KW - detection L1 - SN - N1 - N1 - AB - ER -