@inproceedings{Detecting_Commmunities_via_Simultaneous_Clustering_of_Graphs_and_Folksonomies, author = {Java, Akshay and Joshi, Anupam and Finin, Tim}, title = {Detecting Commmunities via Simultaneous Clustering of Graphs and Folksonomies}, booktitle = {WebKDD 2008 Workshop on Web Mining and Web Usage Analysis}, year = {2008}, note = {To Appear}, keywords = {clustering, community, detection} }

%0 = inproceedings %A = Java, Akshay and Joshi, Anupam and Finin, Tim %B = WebKDD 2008 Workshop on Web Mining and Web Usage Analysis %D = 2008 %T = Detecting Commmunities via Simultaneous Clustering of Graphs and Folksonomies

@inproceedings{1454017, author = {Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis}, title = {Tag recommendations based on tensor dimensionality reduction}, booktitle = {RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems}, publisher = {ACM}, address = {New York, NY, USA}, year = {2008}, pages = {43--50}, url = {http://portal.acm.org/citation.cfm?id=1454017}, doi = {http://doi.acm.org/10.1145/1454008.1454017}, isbn = {978-1-60558-093-7}, keywords = {community, detection, graph, recommender, spectral, tag, theory} }

%0 = inproceedings %A = Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis %B = RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems %C = New York, NY, USA %D = 2008 %I = ACM %T = Tag recommendations based on tensor dimensionality reduction %U = http://portal.acm.org/citation.cfm?id=1454017

@inproceedings{conf/kdd/ChiSZHT07, author = {Chi, Yun and Song, Xiaodan and Zhou, Dengyong and Hino, Koji and Tseng, Belle L.}, title = {Evolutionary spectral clustering by incorporating temporal smoothness.}, editor = {Berkhin, Pavel and Caruana, Rich and Wu, Xindong}, booktitle = {KDD}, publisher = {ACM}, year = {2007}, pages = {153-162}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2007.html#ChiSZHT07}, isbn = {978-1-59593-609-7}, keywords = {clustering, community, detection, spectral} }

%0 = inproceedings %A = Chi, Yun and Song, Xiaodan and Zhou, Dengyong and Hino, Koji and Tseng, Belle L. %B = KDD %D = 2007 %I = ACM %T = Evolutionary spectral clustering by incorporating temporal smoothness. %U = http://dblp.uni-trier.de/db/conf/kdd/kdd2007.html#ChiSZHT07

Recent years have seen that WWW is becoming a flourishing social media which enables individuals to easily share opinions, experiences and expertise at the push of a single button. With the pervasive usage of instant messaging systems and the fundamental shift in the ease of publishing content, social network researchers and graph theory researchers are now concerned with inferring community structures by analyzing the linkage patterns among individuals and web pages. Although the investigation of community structures has motivated many diverse algorithms, most of them are unsuitable for large-scale social networks because of the computational cost. Moreover, in addition to identify the possible community structures, how to define and explain the discovered communities is also significant in many practical scenarios.
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.

@inproceedings{1348552, author = {Du, Nan and Wu, Bin and Pei, Xin and Wang, Bai and Xu, Liutong}, title = {Community detection in large-scale social networks}, booktitle = {WebKDD/SNA-KDD '07: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis}, publisher = {ACM}, address = {New York, NY, USA}, year = {2007}, pages = {16--25}, url = {http://portal.acm.org/citation.cfm?id=1348549.1348552&coll=GUIDE&dl=GUIDE&type=series&idx=SERIES939&part=series&WantType=Proceedings&title=KDD&CFID=17695029&CFTOKEN=22803053}, doi = {http://doi.acm.org/10.1145/1348549.1348552}, isbn = {978-1-59593-848-0}, keywords = {community, complex-network, detection, social-media}, abstract = {Recent years have seen that WWW is becoming a flourishing social media which enables individuals to easily share opinions, experiences and expertise at the push of a single button. With the pervasive usage of instant messaging systems and the fundamental shift in the ease of publishing content, social network researchers and graph theory researchers are now concerned with inferring community structures by analyzing the linkage patterns among individuals and web pages. Although the investigation of community structures has motivated many diverse algorithms, most of them are unsuitable for large-scale social networks because of the computational cost. Moreover, in addition to identify the possible community structures, how to define and explain the discovered communities is also significant in many practical scenarios.
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.
} }

%0 = inproceedings %A = Du, Nan and Wu, Bin and Pei, Xin and Wang, Bai and Xu, Liutong %B = WebKDD/SNA-KDD '07: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis %C = New York, NY, USA %D = 2007 %I = ACM %T = Community detection in large-scale social networks %U = http://portal.acm.org/citation.cfm?id=1348549.1348552&coll=GUIDE&dl=GUIDE&type=series&idx=SERIES939&part=series&WantType=Proceedings&title=KDD&CFID=17695029&CFTOKEN=22803053

@inproceedings{grahl07conceptualKdml, author = {Grahl, Miranda and Hotho, Andreas and Stumme, Gerd}, title = {Conceptual Clustering of Social Bookmark Sites}, editor = {Hinneburg, Alexander}, booktitle = {Workshop Proceedings of Lernen - Wissensentdeckung - Adaptivität (LWA 2007)}, publisher = {Martin-Luther-Universität Halle-Wittenberg}, year = {2007}, pages = {50-54}, url = {http://www.tagora-project.eu/wp-content/2007/06/grahl_iknow07.pdf }, isbn = {978-3-86010-907-6}, keywords = {clustering, community, detection} }

%0 = inproceedings %A = Grahl, Miranda and Hotho, Andreas and Stumme, Gerd %B = Workshop Proceedings of Lernen - Wissensentdeckung - Adaptivität (LWA 2007) %D = 2007 %I = Martin-Luther-Universität Halle-Wittenberg %T = Conceptual Clustering of Social Bookmark Sites %U = http://www.tagora-project.eu/wp-content/2007/06/grahl_iknow07.pdf

@inproceedings{Begelman2006, author = {Begelman, Grigory and Keller, Philipp and Smadja, Frank}, title = {Automated Tag Clustering: Improving search and exploration in the tag space}, booktitle = {Proceedings of the WWW 2006 Workshop on Collaborative Web Tagging Workshop}, address = {Edinburgh}, year = {2006}, url = {http://www.rawsugar.com/www2006/taggingworkshopschedule.html}, keywords = {clustering, community, detection} }

%0 = inproceedings %A = Begelman, Grigory and Keller, Philipp and Smadja, Frank %B = Proceedings of the WWW 2006 Workshop on Collaborative Web Tagging Workshop %C = Edinburgh %D = 2006 %T = Automated Tag Clustering: Improving search and exploration in the tag space %U = http://www.rawsugar.com/www2006/taggingworkshopschedule.html

@article{newman2006fcs, author = {Newman, MEJ}, title = {Finding community structure in networks using the eigenvectors of matrices}, journal = {Physical Review E}, publisher = {APS}, year = {2006}, volume = {74}, number = {3}, pages = {36104}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = APS %T = Finding community structure in networks using the eigenvectors of matrices

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.

@inproceedings{schmitz06-inducing, author = {Schmitz, Patrick}, title = {Inducing Ontology from Flickr Tags}, booktitle = {Proceedings of the Workshop on Collaborative Tagging at WWW2006}, address = {Edinburgh, Scotland}, year = {2006}, url = {http://.citeulike.org/user/ryanshaw/article/740688}, keywords = {community, detection, learning, ontology}, abstract = {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.} }

%0 = inproceedings %A = Schmitz, Patrick %B = Proceedings of the Workshop on Collaborative Tagging at WWW2006 %C = Edinburgh, Scotland %D = 2006 %T = Inducing Ontology from Flickr Tags %U = http://.citeulike.org/user/ryanshaw/article/740688

@article{danon2005ccs, author = {Danon, L. and Diaz-Guilera, A. and Duch, J. and Arenas, A.}, title = {Comparing community structure identification}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, publisher = {Institute of Physics Publishing}, year = {2005}, volume = {9}, pages = {P09008}, keywords = {community, detection} }

%0 = article %A = Danon, L. and Diaz-Guilera, A. and Duch, J. and Arenas, A. %D = 2005 %I = Institute of Physics Publishing %T = Comparing community structure identification

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.

@article{Newman04communityStructure, author = {Newman, M E and Girvan, M}, title = {Finding and evaluating community structure in networks}, journal = {Phys Rev E Stat Nonlin Soft Matter Phys}, year = {2004}, volume = {69}, number = {2}, pages = {026113.1-15}, url = {http://www.ncbi.nlm.nih.gov/pubmed/14995526}, keywords = {detection, modularity, score}, abstract = {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.} }

%0 = article %A = Newman, M E and Girvan, M %D = 2004 %T = Finding and evaluating community structure in networks %U = http://www.ncbi.nlm.nih.gov/pubmed/14995526

@article{newman2004dcs, author = {Newman, MEJ}, title = {Detecting community structure in networks}, journal = {The European Physical Journal B-Condensed Matter}, publisher = {Springer}, year = {2004}, volume = {38}, number = {2}, pages = {321--330}, keywords = {community, detection} }

%0 = article %A = Newman, MEJ %D = 2004 %I = Springer %T = Detecting community structure in networks

@article{1214919, author = {Huang, Xiaodi and Lai, Wei}, title = {Identification of clusters in the Web graph based on link topology}, journal = {Database Engineering and Applications Symposium, 2003. Proceedings. Seventh International}, year = {2003}, pages = { 123-128}, issn = {1098-8068}, keywords = {cluster, community, detection} }

%0 = article %A = Huang, Xiaodi and Lai, Wei %D = 2003 %T = Identification of clusters in the Web graph based on link topology

@article{flake2002soa, author = {Flake, GW and Lawrence, S. and Giles, CL and Coetzee, FM}, title = {Self-organization and identification of Web communities}, journal = {Computer}, year = {2002}, volume = {35}, number = {3}, pages = {66--70}, keywords = {community, detection} }

%0 = article %A = Flake, GW and Lawrence, S. and Giles, CL and Coetzee, FM %D = 2002 %T = Self-organization and identification of Web communities

@inproceedings{coclustering01, author = {Dhillon, Inderjit S.}, title = {Co-clustering documents and words using bipartite spectral graph partitioning}, booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2001}, pages = {269--274}, url = {http://portal.acm.org/citation.cfm?id=502512.502550}, doi = {10.1145/502512.502550}, isbn = {158113391X}, keywords = {community, detection, graph, spectral, theory} }

%0 = inproceedings %A = Dhillon, Inderjit S. %B = KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2001 %I = ACM Press %T = Co-clustering documents and words using bipartite spectral graph partitioning %U = http://portal.acm.org/citation.cfm?id=502512.502550

@inproceedings{conf/icml/WagstaffCRS01, author = {Wagstaff, Kiri and Cardie, Claire and Rogers, Seth and Schrödl, Stefan}, title = {Constrained K-means Clustering with Background Knowledge.}, editor = {Brodley, Carla E. and Danyluk, Andrea Pohoreckyj}, booktitle = {ICML}, publisher = {Morgan Kaufmann}, year = {2001}, pages = {577-584}, url = {http://dblp.uni-trier.de/db/conf/icml/icml2001.html#WagstaffCRS01}, isbn = {1-55860-778-1}, keywords = {clustering, community, constrained, detection, k-means} }

%0 = inproceedings %A = Wagstaff, Kiri and Cardie, Claire and Rogers, Seth and Schrödl, Stefan %B = ICML %D = 2001 %I = Morgan Kaufmann %T = Constrained K-means Clustering with Background Knowledge. %U = http://dblp.uni-trier.de/db/conf/icml/icml2001.html#WagstaffCRS01

@inproceedings{347121, author = {Flake, Gary William and Lawrence, Steve and Giles, C. Lee}, title = {Efficient identification of Web communities}, booktitle = {KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2000}, pages = {150--160}, doi = {http://doi.acm.org/10.1145/347090.347121}, isbn = {1-58113-233-6}, keywords = {community, detection} }

%0 = inproceedings %A = Flake, Gary William and Lawrence, Steve and Giles, C. Lee %B = KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2000 %I = ACM Press %T = Efficient identification of Web communities

@inproceedings{conf/cvpr/ShiM97, author = {Shi, Jianbo and Malik, Jitendra}, title = {Normalized Cuts and Image Segmentation.}, booktitle = {CVPR}, year = {1997}, pages = {731-737}, url = {http://dblp.uni-trier.de/db/conf/cvpr/cvpr1997.html#ShiM97}, keywords = {clustering, community, detection, ncut} }

%0 = inproceedings %A = Shi, Jianbo and Malik, Jitendra %B = CVPR %D = 1997 %T = Normalized Cuts and Image Segmentation. %U = http://dblp.uni-trier.de/db/conf/cvpr/cvpr1997.html#ShiM97

@article{berry1995ula, author = {Berry, M.W. and Dumais, S.T. and O'Brien, G.W.}, title = {Using Linear Algebra for Intelligent Information Retrieval}, journal = {SIAM REVIEW}, publisher = {SIAM SOCIETY FOR INDUSTRIAL AND APPLIED}, year = {1995}, volume = {37}, pages = {573--595}, keywords = {algebra, community, detection, linear, svd, weka} }

%0 = article %A = Berry, M.W. and Dumais, S.T. and O'Brien, G.W. %D = 1995 %I = SIAM SOCIETY FOR INDUSTRIAL AND APPLIED %T = Using Linear Algebra for Intelligent Information Retrieval

@article{journals/tcad/ChanSZ94, author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.}, title = {Spectral K-way ratio-cut partitioning and clustering.}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, year = {1994}, volume = {13}, number = {9}, pages = {1088-1096}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94}, keywords = {community, detection, graph, partitioning, spectral, theory} }

%0 = article %A = Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y. %D = 1994 %T = Spectral K-way ratio-cut partitioning and clustering. %U = http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94

@article{fiedler1973acg, author = {Fiedler, M.}, title = {Algebraic connectivity of graphs}, journal = {Czechoslovak Mathematical Journal}, year = {1973}, volume = {23}, number = {98}, pages = {298--305}, keywords = {community, detection} }

%0 = article %A = Fiedler, M. %D = 1973 %T = Algebraic connectivity of graphs