The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.

@article{Fortunato201075, author = {Fortunato, Santo}, title = {Community detection in graphs}, journal = {Physics Reports}, year = {2010}, volume = {486}, number = {3-5}, pages = {75 - 174}, url = {http://www.sciencedirect.com/science/article/B6TVP-4XPYXF1-1/2/99061fac6435db4343b2374d26e64ac1}, doi = {DOI: 10.1016/j.physrep.2009.11.002}, issn = {0370-1573}, keywords = {community, detection, survey, toread}, abstract = {The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.} }

%0 = article %A = Fortunato, Santo %D = 2010 %T = Community detection in graphs %U = http://www.sciencedirect.com/science/article/B6TVP-4XPYXF1-1/2/99061fac6435db4343b2374d26e64ac1

People share millions of resources (photos, bookmarks, videos, etc.) in Folksonomies (like Flickr, Delicious, Youtube, etc.). To access and share resources, they add keywords called tags to the resources. As the tags are freely chosen keywords, it might not be possible for users to tag their resources with all the relevant tags. As a result, many resources lack sufficient number of relevant tags. The lack of relevant tags results into sparseness of data, and this sparseness of data makes many relevant resources unsearchable against user queries.

@inproceedings{Abbasi09, author = {Abbasi, Rabeeh and Staab, Steffen}, title = {RichVSM: enRiched vector space models for folksonomies}, booktitle = {HT '09: Proceedings of the 20th ACM conference on Hypertext and hypermedia}, publisher = {ACM}, address = {New York, NY, USA}, year = {2009}, pages = {219--228}, url = {http://dx.doi.org/10.1145/1557914.1557952}, doi = {10.1145/1557914.1557952}, isbn = {978-1-60558-486-7}, keywords = {toread}, abstract = {People share millions of resources (photos, bookmarks, videos, etc.) in Folksonomies (like Flickr, Delicious, Youtube, etc.). To access and share resources, they add keywords called tags to the resources. As the tags are freely chosen keywords, it might not be possible for users to tag their resources with all the relevant tags. As a result, many resources lack sufficient number of relevant tags. The lack of relevant tags results into sparseness of data, and this sparseness of data makes many relevant resources unsearchable against user queries.} }

%0 = inproceedings %A = Abbasi, Rabeeh and Staab, Steffen %B = HT '09: Proceedings of the 20th ACM conference on Hypertext and hypermedia %C = New York, NY, USA %D = 2009 %I = ACM %T = RichVSM: enRiched vector space models for folksonomies %U = http://dx.doi.org/10.1145/1557914.1557952

In this paper, we use a partition of the links of a network in order to
cover its community structure. This approach allows for communities to
erlap at nodes, so that nodes may be in more than one community. We do this
making a node partition of the line graph of the original network. In this
y we show that any algorithm which produces a partition of nodes can be used
produce a partition of links. We discuss the role of the degree
terogeneity and propose a weighted version of the line graph in order to
count for this.

@misc{Evans2009, author = {Evans, T. S. and Lambiotte, R.}, title = {Line Graphs, Link Partitions and Overlapping Communities}, year = {2009}, note = {cite arxiv:0903.2181
mment: 9 pages, 7 figures. Version 2 includes minor changes to text and
references and some improved figures}, url = {http://arxiv.org/abs/0903.2181}, keywords = {community, detection, toread}, abstract = { In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes, so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm which produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this. } }

%0 = misc %A = Evans, T. S. and Lambiotte, R. %B = } %C = %D = 2009 %I = %T = Line Graphs, Link Partitions and Overlapping Communities} %U = http://arxiv.org/abs/0903.2181

During the last decade, the science of networks has grown into an enormous
terdisciplinary endeavor, with methods and applications drawn from across the
tural, social, and information sciences. One of the most important and
ominent ideas from network science is the algorithmic detection of
ghtly-connected groups of nodes known as communities. Here we develop a
rmulation to detect communities in a very broad setting by studying general
namical processes on networks. We create a new framework of network quality
nctions that allows us to study the community structure of arbitrary
ltislice networks, which are combinations of individual networks coupled
rough additional links that connect each node in one network slice to itself
other slices. This new framework allows one for the first time to study
mmunity structure in a very general setting that encompasses networks that
olve in time, have multiple types of ties (multiplexity), and have multiple
ales.

@misc{Mucha2009, author = {Mucha, Peter J. and Richardson, Thomas and Macon, Kevin and Porter, Mason A. and Onnela, Jukka-Pekka}, title = {Community Structure in Time-Dependent, Multiscale, and Multiplex
Networks}, year = {2009}, note = {cite arxiv:0911.1824
mment: 23 pages, 3 figures, 1 table}, url = {http://arxiv.org/abs/0911.1824}, keywords = {community, data, detection, dynamic, toread}, abstract = { During the last decade, the science of networks has grown into an enormous interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. One of the most important and prominent ideas from network science is the algorithmic detection of tightly-connected groups of nodes known as communities. Here we develop a formulation to detect communities in a very broad setting by studying general dynamical processes on networks. We create a new framework of network quality functions that allows us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through additional links that connect each node in one network slice to itself in other slices. This new framework allows one for the first time to study community structure in a very general setting that encompasses networks that evolve in time, have multiple types of ties (multiplexity), and have multiple scales. } }

%0 = misc %A = Mucha, Peter J. and Richardson, Thomas and Macon, Kevin and Porter, Mason A. and Onnela, Jukka-Pekka %B = } %C = %D = 2009 %I = %T = Community Structure in Time-Dependent, Multiscale, and Multiplex
Networks} %U = http://arxiv.org/abs/0911.1824

@article{santos2009individual, author = {Santos-Neto, E. and Condon, D. and Andrade, N. and Iamnitchi, A. and Ripeanu, M.}, title = {Individual and social behavior in tagging systems}, booktitle = {Proceedings of the 20th ACM conference on Hypertext and hypermedia}, year = {2009}, pages = {183--192}, url = {http://scholar.google.de/scholar.bib?q=info:78ozoF5AkegJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {folksonomy, link, social, tagging, toread, ur} }

%0 = article %A = Santos-Neto, E. and Condon, D. and Andrade, N. and Iamnitchi, A. and Ripeanu, M. %B = Proceedings of the 20th ACM conference on Hypertext and hypermedia %D = 2009 %T = Individual and social behavior in tagging systems %U = http://scholar.google.de/scholar.bib?q=info:78ozoF5AkegJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

We use the emergent field of complex networks to analyze the network of scientific collaborations between entities (universities, research organizations, industry related companies,...) which collaborate in the context of the so-called framework programme. We demonstrate here that it is a scale-free network with an accelerated growth, which implies that the creation of new collaborations is encouraged. Moreover, these collaborations possess hierarchical modularity. Likewise, we find that the information flow depends on the size of the participants but not on geographical constraints.

@article{Almendral2007675, author = {Almendral, Juan A. and Oliveira, J.G. and López, L. and Mendes, J.F.F. and Sanjuán, Miguel A.F.}, title = {The network of scientific collaborations within the European framework programme}, journal = {Physica A: Statistical Mechanics and its Applications}, year = {2007}, volume = {384}, number = {2}, pages = {675 - 683}, url = {http://www.sciencedirect.com/science/article/B6TVG-4NTJH10-4/2/b209f12299c9e1d367a8298e7d986215}, doi = {DOI: 10.1016/j.physa.2007.05.049}, issn = {0378-4371}, keywords = {analysis, network, social, toread, ur}, abstract = {We use the emergent field of complex networks to analyze the network of scientific collaborations between entities (universities, research organizations, industry related companies,...) which collaborate in the context of the so-called framework programme. We demonstrate here that it is a scale-free network with an accelerated growth, which implies that the creation of new collaborations is encouraged. Moreover, these collaborations possess hierarchical modularity. Likewise, we find that the information flow depends on the size of the participants but not on geographical constraints.} }

%0 = article %A = Almendral, Juan A. and Oliveira, J.G. and López, L. and Mendes, J.F.F. and Sanjuán, Miguel A.F. %D = 2007 %T = The network of scientific collaborations within the European framework programme %U = http://www.sciencedirect.com/science/article/B6TVG-4NTJH10-4/2/b209f12299c9e1d367a8298e7d986215

@article{mislove2007measurement, author = {Mislove, A. and Marcon, M. and Gummadi, K.P. and Druschel, P. and Bhattacharjee, B.}, title = {Measurement and analysis of online social networks}, booktitle = {Proceedings of the 7th ACM SIGCOMM conference on Internet measurement}, year = {2007}, pages = {42}, url = {http://scholar.google.de/scholar.bib?q=info:HmucgVkM3hQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {analysis, folksonomy, link, sna, toread, ur, user} }

%0 = article %A = Mislove, A. and Marcon, M. and Gummadi, K.P. and Druschel, P. and Bhattacharjee, B. %B = Proceedings of the 7th ACM SIGCOMM conference on Internet measurement %D = 2007 %T = Measurement and analysis of online social networks %U = http://scholar.google.de/scholar.bib?q=info:HmucgVkM3hQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

@article{prieur2007strength, author = {Prieur, C. and Cardon, D. and Beuscart, J.S. and Pissard, N. and Pons, P.}, title = {The strength of weak cooperation: A case study on Flickr}, journal = {h http://arxiv. org/ftp/arxiv/papers/0802/0802.2317. pdf}, year = {2007}, url = {http://scholar.google.de/scholar.bib?q=info:2JNrrjb49XMJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=1}, keywords = {flickr, folksonomy, link, social, toread, ur} }

%0 = article %A = Prieur, C. and Cardon, D. and Beuscart, J.S. and Pissard, N. and Pons, P. %D = 2007 %T = The strength of weak cooperation: A case study on Flickr %U = http://scholar.google.de/scholar.bib?q=info:2JNrrjb49XMJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=1

@article{van2007flickr, author = {Zwol, R. Van}, title = {Flickr: Who is Looking?}, booktitle = {Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence}, year = {2007}, pages = {184--190}, url = {http://scholar.google.de/scholar.bib?q=info:YMoA8DCZLoMJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=5}, keywords = {flickr, folksonomy, link, social, toread, ur} }

%0 = article %A = Zwol, R. Van %B = Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence %D = 2007 %T = Flickr: Who is Looking? %U = http://scholar.google.de/scholar.bib?q=info:YMoA8DCZLoMJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=5

In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.We present a simple model of network growth which captures these aspects of component structure. The model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network.

@inproceedings{1150476, author = {Kumar, Ravi and Novak, Jasmine and Tomkins, Andrew}, title = {Structure and evolution of online social networks}, booktitle = {KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM}, address = {New York, NY, USA}, year = {2006}, pages = {611--617}, url = {http://portal.acm.org/citation.cfm?id=1150402.1150476}, doi = {http://doi.acm.org/10.1145/1150402.1150476}, isbn = {1-59593-339-5}, keywords = {analysis, link, network, sna, structure, toread, ur, user}, abstract = {In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.We present a simple model of network growth which captures these aspects of component structure. The model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network.} }

%0 = inproceedings %A = Kumar, Ravi and Novak, Jasmine and Tomkins, Andrew %B = KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2006 %I = ACM %T = Structure and evolution of online social networks %U = http://portal.acm.org/citation.cfm?id=1150402.1150476

@article{lerman2006social, author = {Lerman, K. and Jones, L.}, title = {Social browsing on flickr}, journal = {Arxiv preprint cs/0612047}, year = {2006}, url = {http://scholar.google.de/scholar.bib?q=info:4ZJ0zK6yr5wJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {flickr, folksonomy, link, social, tagging, toread, ur} }

%0 = article %A = Lerman, K. and Jones, L. %D = 2006 %T = Social browsing on flickr %U = http://scholar.google.de/scholar.bib?q=info:4ZJ0zK6yr5wJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

@article{menczer2004lexical, author = {Menczer, F.}, title = {Lexical and semantic clustering by web links}, journal = {Journal of the American Society for Information Science and Technology}, publisher = {Citeseer}, year = {2004}, volume = {55}, number = {14}, pages = {1261--1269}, url = {http://scholar.google.de/scholar.bib?q=info:qmPuziT0_h0J:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {link, locality, network, structure, topical, toread, ur} }

%0 = article %A = Menczer, F. %D = 2004 %I = Citeseer %T = Lexical and semantic clustering by web links %U = http://scholar.google.de/scholar.bib?q=info:qmPuziT0_h0J:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

@article{Blei+Ng+Jordan:03a, author = {Blei, David M. and Ng, Andrew Y. and Jordan, Michael I.}, title = {Latent Dirichlet Allocation}, journal = {Journal of Machine Learning Research}, year = {2003}, volume = {3}, pages = {993--1022}, keywords = {lda, toread} }

%0 = article %A = Blei, David M. and Ng, Andrew Y. and Jordan, Michael I. %D = 2003 %T = Latent Dirichlet Allocation

@inproceedings{dhillon:mallela:modha:03, author = {Dhillon, I. S. and Mallela, S. and Modha, D. S.}, title = {Information-Theoretic Co-Clustering}, booktitle = {Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003)}, year = {2003}, pages = {89--98}, url = {/brokenurl#citeseer.ist.psu.edu/dhillon03informationtheoretic.html}, keywords = {clustering, co-clustering, dhillon, information, theory, toread} }

%0 = inproceedings %A = Dhillon, I. S. and Mallela, S. and Modha, D. S. %B = Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003) %D = 2003 %T = Information-Theoretic Co-Clustering %U = /brokenurl#citeseer.ist.psu.edu/dhillon03informationtheoretic.html

Abstract  After 30 years of research, co-citation analysis has become the dominant method for the empirical study of the structures
scientific communication. There is a considerable variety of methods and, at the same time, a lack of methodological evaluation.This paper summarizes the present state of co-citation analysis and presents several methods of clustering references. Thedatabase used is a selection of 2,114 documents in the field of organization studies from 1986-2000. The evaluative studyshows that the choice of methods has a strong impact on the results created. It also shows that the methods of cluster andfactor analysis hitherto used have only a limited value in differentiating clearly between schools of scientific research- the 'invisible colleges'.

@article{markus2003cocitation, author = {Gmür, Markus}, title = {Co-citation analysis and the search for invisible colleges: A methodological evaluation}, journal = {Scientometrics}, year = {2003}, volume = {57}, number = {1}, pages = {27--57}, url = {http://dx.doi.org/10.1023/A:1023619503005}, keywords = {community, detection, evaluation, lwa, toread}, abstract = {Abstract  After 30 years of research, co-citation analysis has become the dominant method for the empirical study of the structures of scientific communication. There is a considerable variety of methods and, at the same time, a lack of methodological evaluation.This paper summarizes the present state of co-citation analysis and presents several methods of clustering references. Thedatabase used is a selection of 2,114 documents in the field of organization studies from 1986-2000. The evaluative studyshows that the choice of methods has a strong impact on the results created. It also shows that the methods of cluster andfactor analysis hitherto used have only a limited value in differentiating clearly between schools of scientific research- the 'invisible colleges'.} }

%0 = article %A = Gmür, Markus %D = 2003 %T = Co-citation analysis and the search for invisible colleges: A methodological evaluation %U = http://dx.doi.org/10.1023/A:1023619503005

@article{broder2000graph, author = {Broder, A. and Kumar, R. and Maghoul, F. and Raghavan, P. and Rajagopalan, S. and Stata, R. and Tomkins, A. and Wiener, J.}, title = {Graph structure in the web}, journal = {Computer Networks}, publisher = {Elsevier}, year = {2000}, volume = {33}, number = {1-6}, pages = {309--320}, url = {http://scholar.google.de/scholar.bib?q=info:XK3rB5QCtqgJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {analysis, network, scc, structure, toread, ur, web} }

%0 = article %A = Broder, A. and Kumar, R. and Maghoul, F. and Raghavan, P. and Rajagopalan, S. and Stata, R. and Tomkins, A. and Wiener, J. %D = 2000 %I = Elsevier %T = Graph structure in the web %U = http://scholar.google.de/scholar.bib?q=info:XK3rB5QCtqgJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

@inproceedings{lee00algorithms, author = {Lee, Daniel D. and Seung, H. Sebastian}, title = {Algorithms for Non-negative Matrix Factorization}, booktitle = {NIPS}, year = {2000}, pages = {556-562}, url = {/brokenurl#citeseer.ist.psu.edu/lee01algorithms.html}, keywords = {factorization, matrix, multi, toread, view} }

%0 = inproceedings %A = Lee, Daniel D. and Seung, H. Sebastian %B = NIPS %D = 2000 %T = Algorithms for Non-negative Matrix Factorization %U = /brokenurl#citeseer.ist.psu.edu/lee01algorithms.html

@article{lee99, author = {Lee, Daniel D. and Seung, H. Sebastian}, title = {Learning the parts of objects by nonnegative matrix factorization}, journal = {Nature}, year = {1999}, volume = {401}, pages = {788--791}, keywords = {clustering, factorization, matrix, multi, toread, view} }

%0 = article %A = Lee, Daniel D. and Seung, H. Sebastian %D = 1999 %T = Learning the parts of objects by nonnegative matrix factorization