@incollection{ADHMS:12, author = {Atzmueller, Martin and Doerfel, Stephan and Hotho, Andreas and Mitzlaff, Folke and Stumme, Gerd}, title = {Face-to-Face Contacts at a Conference: Dynamics of Communities and Roles}, booktitle = {Modeling and Mining Ubiquitous Social Media}, series = {LNAI}, publisher = {Springer Verlag}, address = {Heidelberg, Germany}, year = {2012}, volume = {7472}, url = {http://www.kde.cs.uni-kassel.de/atzmueller/paper/atzmueller-face-to-face-contacts-dynamics-lnai-2012.pdf}, keywords = {2012, community, contacts, dynamics, myown} }

%0 = incollection %A = Atzmueller, Martin and Doerfel, Stephan and Hotho, Andreas and Mitzlaff, Folke and Stumme, Gerd %B = Modeling and Mining Ubiquitous Social Media %C = Heidelberg, Germany %D = 2012 %I = Springer Verlag %T = Face-to-Face Contacts at a Conference: Dynamics of Communities and Roles %U = http://www.kde.cs.uni-kassel.de/atzmueller/paper/atzmueller-face-to-face-contacts-dynamics-lnai-2012.pdf

@inproceedings{ADHMS:11, author = {Atzmueller, Martin and Doerfel, Stephan and Hotho, Andreas and Mitzlaff, Folke and Stumme, Gerd}, title = {Face-to-Face Contacts during a Conference: Communities, Roles, and Key Players}, booktitle = {Proc. Workshop on Mining Ubiquitous and Social Environments (MUSE 2011) at ECML/PKDD 2011}, year = {2011}, keywords = {2011, analysis, communities, community, discovery, knowledge, myown, rfid} }

%0 = inproceedings %A = Atzmueller, Martin and Doerfel, Stephan and Hotho, Andreas and Mitzlaff, Folke and Stumme, Gerd %B = Proc. Workshop on Mining Ubiquitous and Social Environments (MUSE 2011) at ECML/PKDD 2011 %D = 2011 %T = Face-to-Face Contacts during a Conference: Communities, Roles, and Key Players

@inproceedings{mitzlaff2011community, author = {Mitzlaff, Folke and Atzmueller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd}, title = {Community Assessment using Evidence Networks}, booktitle = {Analysis of Social Media and Ubiquitous Data}, series = {LNAI}, year = {2011}, volume = {6904}, keywords = {2011, community, evaluation, knowledge, mining, myown} }

%0 = inproceedings %A = Mitzlaff, Folke and Atzmueller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd %B = Analysis of Social Media and Ubiquitous Data %D = 2011 %T = Community Assessment using Evidence Networks

Detecting clusters or communities in large real-world graphs such as large
cial or information networks is a problem of considerable interest. In
actice, one typically chooses an objective function that captures the
tuition of a network cluster as set of nodes with better internal
nnectivity than external connectivity, and then one applies approximation
gorithms or heuristics to extract sets of nodes that are related to the
jective function and that "look like" good communities for the application of
terest. In this paper, we explore a range of network community detection
thods in order to compare them and to understand their relative performance
d the systematic biases in the clusters they identify. We evaluate several
mmon objective functions that are used to formalize the notion of a network
mmunity, and we examine several different classes of approximation algorithms
at aim to optimize such objective functions. In addition, rather than simply
xing an objective and asking for an approximation to the best cluster of any
ze, we consider a size-resolved version of the optimization problem.
nsidering community quality as a function of its size provides a much finer
ns with which to examine community detection algorithms, since objective
nctions and approximation algorithms often have non-obvious size-dependent
havior.

@misc{Leskovec2010, author = {Leskovec, Jure and Lang, Kevin J. and Mahoney, Michael W.}, title = {Empirical Comparison of Algorithms for Network Community Detection}, year = {2010}, note = {cite arxiv:1004.3539
}, url = {http://arxiv.org/abs/1004.3539}, keywords = {clustering, community, comparision, empirical, evaluation, graph, toread}, abstract = { Detecting clusters or communities in large real-world graphs such as large
cial or information networks is a problem of considerable interest. In
actice, one typically chooses an objective function that captures the
tuition of a network cluster as set of nodes with better internal
nnectivity than external connectivity, and then one applies approximation
gorithms or heuristics to extract sets of nodes that are related to the
jective function and that "look like" good communities for the application of
terest. In this paper, we explore a range of network community detection
thods in order to compare them and to understand their relative performance
d the systematic biases in the clusters they identify. We evaluate several
mmon objective functions that are used to formalize the notion of a network
mmunity, and we examine several different classes of approximation algorithms
at aim to optimize such objective functions. In addition, rather than simply
xing an objective and asking for an approximation to the best cluster of any
ze, we consider a size-resolved version of the optimization problem.
nsidering community quality as a function of its size provides a much finer
ns with which to examine community detection algorithms, since objective
nctions and approximation algorithms often have non-obvious size-dependent
havior.
} }

%0 = misc %A = Leskovec, Jure and Lang, Kevin J. and Mahoney, Michael W. %D = 2010 %T = Empirical Comparison of Algorithms for Network Community Detection %U = http://arxiv.org/abs/1004.3539

Community mining is a prominent approach for identifying (user) communities in social and ubiquitous contexts. While there are a variety of methods for community mining and detection, the effective evaluation and validation of the mined communities is usually non-trivial. Often there is no evaluation data at hand in order to validate the discovered groups. This paper proposes evidence networks using implicit information for the evaluation of communities. The presented evaluation approach is based on the idea of reconstructing existing social structures for the assessment and evaluation of a given clustering. We analyze and compare the presented evidence networks using user data from the real-world social
okmarking application BibSonomy. The results indicate that the evidence
tworks reflect the relative rating of the explicit ones very well.

@inproceedings{mitzlaff2010community, author = {Mitzlaff, Folke and Atzmüller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd}, title = {Community Assessment using Evidence Networks}, booktitle = {Proceedings of the Workshop on Mining Ubiquitous and Social Environments (MUSE2010)}, address = {Barcelona, Spain}, year = {2010}, url = {http://www.kde.cs.uni-kassel.de/ws/muse2010}, keywords = {2010, assessment, bibsonomy, community, evidence, myown, networks}, abstract = {Community mining is a prominent approach for identifying (user) communities in social and ubiquitous contexts. While there are a variety of methods for community mining and detection, the effective evaluation and validation of the mined communities is usually non-trivial. Often there is no evaluation data at hand in order to validate the discovered groups. This paper proposes evidence networks using implicit information for the evaluation of communities. The presented evaluation approach is based on the idea of reconstructing existing social structures for the assessment and evaluation of a given clustering. We analyze and compare the presented evidence networks using user data from the real-world social
okmarking application BibSonomy. The results indicate that the evidence
tworks reflect the relative rating of the explicit ones very well.} }

%0 = inproceedings %A = Mitzlaff, Folke and Atzmüller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd %B = Proceedings of the Workshop on Mining Ubiquitous and Social Environments (MUSE2010) %C = Barcelona, Spain %D = 2010 %T = Community Assessment using Evidence Networks %U = http://www.kde.cs.uni-kassel.de/ws/muse2010

Web 2.0 is transforming the internet: Information consumers become
formation producers and consumers at the same time. In virtual places like
cebook, Youtube, discussion boards and weblogs diversificated topics, groups
d issues are propagated and discussed. Today an internet user is a member of
ts of communities at different virtual places. "Real life" group membership
d group behavior has been analyzed in science intensively in the last
cades. Most interestingly, to our knowledge, user roles and behavior have not
en adapted to the modern internet. In this work, we give a short overview of
aditional community roles. We adapt those models and apply them to virtual
line communities. We suggest a community membership life cycle model
scribing roles a user can take during his membership in a community. Our
del is systematic and generic; it can be adapted to concrete communities in
e web. The knowledge of a community's life cycle allows influencing the group
ructure: Stage transitions can be supported or harmed, e.g. to strengthen the
nding of a user to a site and keep communities alive.

@misc{Sonnenbichler2010, author = {Sonnenbichler, Andreas C.}, title = {A Community Membership Life Cycle Model}, year = {2010}, note = {cite arxiv:1006.4271
mment: Presented at the International Network For Social Network Analysis
(INSNA): Sunbelt Conference 2009, San Diego, California, USA. 9 pages, 6
figures}, url = {http://arxiv.org/abs/1006.4271}, keywords = {community, membership, model, toread}, abstract = { Web 2.0 is transforming the internet: Information consumers become
formation producers and consumers at the same time. In virtual places like
cebook, Youtube, discussion boards and weblogs diversificated topics, groups
d issues are propagated and discussed. Today an internet user is a member of
ts of communities at different virtual places. "Real life" group membership
d group behavior has been analyzed in science intensively in the last
cades. Most interestingly, to our knowledge, user roles and behavior have not
en adapted to the modern internet. In this work, we give a short overview of
aditional community roles. We adapt those models and apply them to virtual
line communities. We suggest a community membership life cycle model
scribing roles a user can take during his membership in a community. Our
del is systematic and generic; it can be adapted to concrete communities in
e web. The knowledge of a community's life cycle allows influencing the group
ructure: Stage transitions can be supported or harmed, e.g. to strengthen the
nding of a user to a site and keep communities alive.
} }

%0 = misc %A = Sonnenbichler, Andreas C. %D = 2010 %T = A Community Membership Life Cycle Model %U = http://arxiv.org/abs/1006.4271

The past decade has witnessed the emergence of participatory Web and social media, bringing people together in many creative ways. Millions of users are playing, tagging, working, and socializing online, demonstrating new forms of collaboration, communication, and intelligence that were hardly imaginable just a short time ago. Social media also helps reshape business models, sway opinions and emotions, and opens up numerous possibilities to study human interaction and collective behavior in an unparalleled scale. This lecture, from a data mining perspective, introduces characteristics of social media, reviews representative tasks of computing with social media, and illustrates associated challenges. It introduces basic concepts, presents state-of-the-art algorithms with easy-to-understand examples, and recommends effective evaluation methods. In particular, we discuss graph-based community detection techniques and many important extensions that handle dynamic, heterogeneous networks in social media. We also demonstrate how discovered patterns of communities can be used for social media mining. The concepts, algorithms, and methods presented in this lecture can help harness the power of social media and support building socially-intelligent systems. This book is an accessible introduction to the study of community detection and mining in social media. It is an essential reading for students, researchers, and practitioners in disciplines and applications where social media is a key source of data that piques our curiosity to understand, manage, innovate, and excel.
This book is supported by additional materials, including lecture slides, the complete set of figures, key references, some toy data sets used in the book, and the source code of representative algorithms. The readers are encouraged to visit the book website for the latest information.
Table of Contents: Social Media and Social Computing / Nodes, Ties, and Influence / Community Detection and Evaluation / Communities in Heterogeneous Networks / Social Media Mining

@book{noauthororeditoryahoo, author = {Tang‌, Lei and Liu‌, Huan}, title = {Community Detection and Mining in Social Media}, year = {2010}, url = {http://www.morganclaypool.com/doi/abs/10.2200/S00298ED1V01Y201009DMK003}, doi = {10.2200/S00298ED1V01Y201009DMK003}, keywords = {community, detection, lecture, media, social, toread}, abstract = {The past decade has witnessed the emergence of participatory Web and social media, bringing people together in many creative ways. Millions of users are playing, tagging, working, and socializing online, demonstrating new forms of collaboration, communication, and intelligence that were hardly imaginable just a short time ago. Social media also helps reshape business models, sway opinions and emotions, and opens up numerous possibilities to study human interaction and collective behavior in an unparalleled scale. This lecture, from a data mining perspective, introduces characteristics of social media, reviews representative tasks of computing with social media, and illustrates associated challenges. It introduces basic concepts, presents state-of-the-art algorithms with easy-to-understand examples, and recommends effective evaluation methods. In particular, we discuss graph-based community detection techniques and many important extensions that handle dynamic, heterogeneous networks in social media. We also demonstrate how discovered patterns of communities can be used for social media mining. The concepts, algorithms, and methods presented in this lecture can help harness the power of social media and support building socially-intelligent systems. This book is an accessible introduction to the study of community detection and mining in social media. It is an essential reading for students, researchers, and practitioners in disciplines and applications where social media is a key source of data that piques our curiosity to understand, manage, innovate, and excel.
This book is supported by additional materials, including lecture slides, the complete set of figures, key references, some toy data sets used in the book, and the source code of representative algorithms. The readers are encouraged to visit the book website for the latest information.
Table of Contents: Social Media and Social Computing / Nodes, Ties, and Influence / Community Detection and Evaluation / Communities in Heterogeneous Networks / Social Media Mining } }

%0 = book %A = Tang‌, Lei and Liu‌, Huan %D = 2010 %T = Community Detection and Mining in Social Media %U = http://www.morganclaypool.com/doi/abs/10.2200/S00298ED1V01Y201009DMK003

@inproceedings{conf/icdm/TangWL09, author = {Tang, Lei and Wang, Xufei and Liu, Huan}, title = {Uncoverning Groups via Heterogeneous Interaction Analysis.}, editor = {Wang, Wei and Kargupta, Hillol and Ranka, Sanjay and Yu, Philip S. and Wu, Xindong}, booktitle = {ICDM}, publisher = {IEEE Computer Society}, year = {2009}, pages = {503-512}, url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.7384&rep=rep1&type=pdf}, isbn = {978-0-7695-3895-2}, keywords = {clustering, community, toread} }

%0 = inproceedings %A = Tang, Lei and Wang, Xufei and Liu, Huan %B = ICDM %D = 2009 %I = IEEE Computer Society %T = Uncoverning Groups via Heterogeneous Interaction Analysis. %U = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.7384&rep=rep1&type=pdf

In many social media applications, a small fraction of the members are highly linked while most are sparsely connected to the network. Such a skewed distribution is sometimes referred to as the"long tail". Popular applications like meme trackers and content aggregators mine for information from only the popular blogs located at the head of this curve. On the other hand, the long tail contains large volumes of interesting information and niches. The question we address in this work is how best to approximate the community membership of entities in the long tail using only a small percentage of the entire graph structure. Our technique utilizes basic linear algebra manipulations and spectral methods. It has the advantage of quickly and efficiently finding a reasonable approximation of the community structure of the overall network. Such a method has significant applications in blog analysis engines as well as social media monitoring tools in general.

@inproceedings{Approximating2008Java, author = {Java, Akshay and Joshi, Anupam and FininBook, Tim}, title = {Approximating the Community Structure of the Long Tail}, booktitle = {Proceedings of the Second International Conference on Weblogs and Social Media(ICWSM 2008)}, publisher = {AAAI Press}, year = {2008}, url = {http://ebiquity.umbc.edu/paper/html/id/381/Approximating-the-Community-Structure-of-the-Long-Tail}, keywords = {clustering, community, detection, svd, toread}, abstract = {In many social media applications, a small fraction of the members are highly linked while most are sparsely connected to the network. Such a skewed distribution is sometimes referred to as the"long tail". Popular applications like meme trackers and content aggregators mine for information from only the popular blogs located at the head of this curve. On the other hand, the long tail contains large volumes of interesting information and niches. The question we address in this work is how best to approximate the community membership of entities in the long tail using only a small percentage of the entire graph structure. Our technique utilizes basic linear algebra manipulations and spectral methods. It has the advantage of quickly and efficiently finding a reasonable approximation of the community structure of the overall network. Such a method has significant applications in blog analysis engines as well as social media monitoring tools in general. } }

%0 = inproceedings %A = Java, Akshay and Joshi, Anupam and FininBook, Tim %B = Proceedings of the Second International Conference on Weblogs and Social Media(ICWSM 2008) %D = 2008 %I = AAAI Press %T = Approximating the Community Structure of the Long Tail %U = http://ebiquity.umbc.edu/paper/html/id/381/Approximating-the-Community-Structure-of-the-Long-Tail

@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 = {clusterig, community, detection, folksonomy, toread} }

%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

The success and popularity of social network systems, such as del.icio.us, Facebook, MySpace, and YouTube, have generated many interesting and challenging problems to the research community. Among others, discovering social interests shared by groups of users is very important because it helps to connect people with common interests and encourages people to contribute and share more contents. The main challenge to solving this problem comes from the diffi- culty of detecting and representing the interest of the users. The existing approaches are all based on the online connections of users and so unable to identify the common interest of users who have no online connections. In this paper, we propose a novel social interest discovery approach based on user-generated tags. Our approach is motivated by the key observation that in a social network, human users tend to use descriptive tags to annotate the contents that they are interested in. Our analysis on a large amount of real-world traces reveals that in general, user-generated tags are consistent with the web content they are attached to, while more concise and closer to the understanding and judgments of human users about the content. Thus, patterns of frequent co-occurrences of user tags can be used to characterize and capture topics of user interests. We have developed an Internet Social Interest Discovery system, ISID, to discover the common user interests and cluster users and their saved URLs by different interest topics. Our evaluation shows that ISID can effectively cluster similar documents by interest topics and discover user communities with common interests no matter if they have any online connections.

@inproceedings{xin2008www, author = {Li, Xin and Guo, Lei and Zhao, Yihong E.}, title = {Tag-based Social Interest Discovery}, booktitle = {Proceedings of the 17th International World Wide Web Conference}, publisher = {ACM}, year = {2008}, pages = {675-684}, url = {http://www2008.org/papers/pdf/p675-liA.pdf}, keywords = {***, association, clustering, community, del.icio.us, detection, folksonomy, rules}, abstract = {The success and popularity of social network systems, such as del.icio.us, Facebook, MySpace, and YouTube, have generated many interesting and challenging problems to the research community. Among others, discovering social interests shared by groups of users is very important because it helps to connect people with common interests and encourages people to contribute and share more contents. The main challenge to solving this problem comes from the diffi- culty of detecting and representing the interest of the users. The existing approaches are all based on the online connections of users and so unable to identify the common interest of users who have no online connections. In this paper, we propose a novel social interest discovery approach based on user-generated tags. Our approach is motivated by the key observation that in a social network, human users tend to use descriptive tags to annotate the contents that they are interested in. Our analysis on a large amount of real-world traces reveals that in general, user-generated tags are consistent with the web content they are attached to, while more concise and closer to the understanding and judgments of human users about the content. Thus, patterns of frequent co-occurrences of user tags can be used to characterize and capture topics of user interests. We have developed an Internet Social Interest Discovery system, ISID, to discover the common user interests and cluster users and their saved URLs by different interest topics. Our evaluation shows that ISID can effectively cluster similar documents by interest topics and discover user communities with common interests no matter if they have any online connections.} }

%0 = inproceedings %A = Li, Xin and Guo, Lei and Zhao, Yihong E. %B = Proceedings of the 17th International World Wide Web Conference %D = 2008 %I = ACM %T = Tag-based Social Interest Discovery %U = http://www2008.org/papers/pdf/p675-liA.pdf

@inproceedings{1281269, author = {Tantipathananandh, Chayant and Berger-Wolf, Tanya and Kempe, David}, title = {A framework for community identification in dynamic social networks}, booktitle = {KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM}, address = {New York, NY, USA}, year = {2007}, pages = {717--726}, url = {http://portal.acm.org/citation.cfm?doid=1281192.1281269}, doi = {http://doi.acm.org/10.1145/1281192.1281269}, isbn = {978-1-59593-609-7}, keywords = {clustering, community, detection, graph, toread} }

%0 = inproceedings %A = Tantipathananandh, Chayant and Berger-Wolf, Tanya and Kempe, David %B = KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2007 %I = ACM %T = A framework for community identification in dynamic social networks %U = http://portal.acm.org/citation.cfm?doid=1281192.1281269

@inproceedings{conf/kdd/BackstromHKL06, author = {Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang}, title = {Group formation in large social networks: membership, growth, and evolution.}, editor = {Eliassi-Rad, Tina and Ungar, Lyle H. and Craven, Mark and Gunopulos, Dimitrios}, booktitle = {KDD}, publisher = {ACM}, year = {2006}, pages = {44-54}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06}, isbn = {1-59593-339-5}, keywords = {social, toread, evolution, community, network} }

%0 = inproceedings %A = Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang %B = KDD %D = 2006 %I = ACM %T = Group formation in large social networks: membership, growth, and evolution. %U = http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06

@inproceedings{jaeschke06wege, author = {Jäschke, Robert and Hotho, Andreas and Schmitz, Christoph and Stumme, Gerd}, title = {Wege zur Entdeckung von Communities in Folksonomies}, editor = {Braß, Stefan and Hinneburg, Alexander}, booktitle = {Proc. 18. Workshop Grundlagen von Datenbanken}, publisher = {Martin-Luther-Universität }, address = {Halle-Wittenberg}, year = {2006}, pages = {80-84}, keywords = {2006, folksonomy, bibsonomy, myown, community} }

%0 = inproceedings %A = Jäschke, Robert and Hotho, Andreas and Schmitz, Christoph and Stumme, Gerd %B = Proc. 18. Workshop Grundlagen von Datenbanken %C = Halle-Wittenberg %D = 2006 %I = Martin-Luther-Universität %T = Wege zur Entdeckung von Communities in Folksonomies

@inproceedings{conf/pkdd/CaiSHYH05, author = {Cai, Deng and Shao, Zheng and He, Xiaofei and Yan, Xifeng and Han, Jiawei}, title = {Community Mining from Multi-relational Networks.}, editor = {Jorge, Alípio and Torgo, Luís and Brazdil, Pavel and Camacho, Rui and Gama, João}, booktitle = {PKDD}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, year = {2005}, volume = {3721}, pages = {445-452}, url = {http://dblp.uni-trier.de/db/conf/pkdd/pkdd2005.html#CaiSHYH05}, isbn = {3-540-29244-6}, keywords = {clustering, community, detection, toread} }

%0 = inproceedings %A = Cai, Deng and Shao, Zheng and He, Xiaofei and Yan, Xifeng and Han, Jiawei %B = PKDD %D = 2005 %I = Springer %T = Community Mining from Multi-relational Networks. %U = http://dblp.uni-trier.de/db/conf/pkdd/pkdd2005.html#CaiSHYH05

@article{clauset-2004-70, author = {Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher}, title = {Finding community structure in very large networks}, journal = {Physical Review E}, year = {2004}, volume = {70}, pages = {066111}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0408187}, keywords = {clustering, community, large, networks, toread} }

%0 = article %A = Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher %D = 2004 %T = Finding community structure in very large networks %U = http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0408187

The investigation of community structures in networks is an important issue
many domains and disciplines. This problem is relevant for social tasks
bjective analysis of relationships on the web), biological inquiries
unctional studies in metabolic, cellular or protein networks) or
chnological problems (optimization of large infrastructures). Several types
algorithm exist for revealing the community structure in networks, but a
neral and quantitative definition of community is still lacking, leading to
intrinsic difficulty in the interpretation of the results of the algorithms
thout any additional non-topological information. In this paper we face this
oblem by introducing two quantitative definitions of community and by showing
w they are implemented in practice in the existing algorithms. In this way
e algorithms for the identification of the community structure become fully
lf-contained. Furthermore, we propose a new local algorithm to detect
mmunities which outperforms the existing algorithms with respect to the
mputational cost, keeping the same level of reliability. The new algorithm is
sted on artificial and real-world graphs. In particular we show the
plication of the new algorithm to a network of scientific collaborations,
ich, for its size, can not be attacked with the usual methods. This new class
local algorithms could open the way to applications to large-scale
chnological and biological applications.

@misc{citeulike:341233, author = {Radicchi, Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico}, title = {Defining and identifying communities in networks}, year = {2004}, url = {http://arxiv.org/abs/cond-mat/0309488}, keywords = {clustering, folksonomy, toread, graph, community}, abstract = {The investigation of community structures in networks is an important issue
many domains and disciplines. This problem is relevant for social tasks
bjective analysis of relationships on the web), biological inquiries
unctional studies in metabolic, cellular or protein networks) or
chnological problems (optimization of large infrastructures). Several types
algorithm exist for revealing the community structure in networks, but a
neral and quantitative definition of community is still lacking, leading to
intrinsic difficulty in the interpretation of the results of the algorithms
thout any additional non-topological information. In this paper we face this
oblem by introducing two quantitative definitions of community and by showing
w they are implemented in practice in the existing algorithms. In this way
e algorithms for the identification of the community structure become fully
lf-contained. Furthermore, we propose a new local algorithm to detect
mmunities which outperforms the existing algorithms with respect to the
mputational cost, keeping the same level of reliability. The new algorithm is
sted on artificial and real-world graphs. In particular we show the
plication of the new algorithm to a network of scientific collaborations,
ich, for its size, can not be attacked with the usual methods. This new class
local algorithms could open the way to applications to large-scale
chnological and biological applications.} }

%0 = misc %A = Radicchi, Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico %D = 2004 %T = Defining and identifying communities in networks %U = http://arxiv.org/abs/cond-mat/0309488

@article{reichardt-2004-93, author = {Reichardt, Joerg and Bornholdt, Stefan}, title = {Detecting fuzzy community structures in complex networks with a Potts model}, journal = {Physical Review Letters}, year = {2004}, volume = {93}, pages = {218701}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0402349}, keywords = {toread, detection, community} }

%0 = article %A = Reichardt, Joerg and Bornholdt, Stefan %D = 2004 %T = Detecting fuzzy community structures in complex networks with a Potts model %U = http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0402349

@article{newman03fast, author = {Newman, M.E.J.}, title = {Fast algorithm for detecting community structure in networks}, journal = {Physical Review E}, year = {2003}, volume = {69}, url = {http://arxiv.org/abs/cond-mat/0309508}, keywords = {algorithm, clustering, community, fast, networks} }

%0 = article %A = Newman, M.E.J. %D = 2003 %T = Fast algorithm for detecting community structure in networks %U = http://arxiv.org/abs/cond-mat/0309508

@article{346336, author = {Staab, S. and Angele, J. and Decker, S. and Erdmann, M. and Hotho, A. and Maedche, A. and Schnurr, H.-P. and Studer, R. and Sure, Y.}, title = {Semantic community Web portals}, journal = {Comput. Netw.}, publisher = {Elsevier North-Holland, Inc.}, address = {New York, NY, USA}, year = {2000}, volume = {33}, number = {1-6}, pages = {473--491}, url = {http://portal.acm.org/citation.cfm?id=346241.346336&coll=GUIDE&dl=GUIDE&CFID=7705918&CFTOKEN=32369470}, doi = {http://dx.doi.org/10.1016/S1389-1286(00)00039-6}, issn = {1389-1286}, keywords = {community, semantic} }

%0 = article %A = Staab, S. and Angele, J. and Decker, S. and Erdmann, M. and Hotho, A. and Maedche, A. and Schnurr, H.-P. and Studer, R. and Sure, Y. %C = New York, NY, USA %D = 2000 %I = Elsevier North-Holland, Inc. %T = Semantic community Web portals %U = http://portal.acm.org/citation.cfm?id=346241.346336&coll=GUIDE&dl=GUIDE&CFID=7705918&CFTOKEN=32369470