Exploring recent developments in spectral clustering, we discovered that relaxing a spectral reformulation of Newman's Q-measure (a measure that may guide the search for-and help to evaluate the fit of - community structures in networks) yields a new framework for use in detecting fuzzy communities and identifying so-called unstable nodes. In this note, we present and illustrate this approach, which we expect to further enhance our understanding of the intrinsic structure of networks and of network-based clustering procedures. We applied a variation of the fuzzy k-means algorithm, an instance of our framework, to two social networks. The computational results illustrate its potential.

@article{Jiang20091479, author = {Jiang, Jeffrey Q. and Dress, Andreas W.M. and Yang, Genke}, title = {A spectral clustering-based framework for detecting community structures in complex networks}, journal = {Applied Mathematics Letters}, year = {2009}, volume = {22}, number = {9}, pages = {1479 - 1482}, url = {http://www.sciencedirect.com/science/article/B6TY9-4W6XYH5-5/2/693a9ed19784792496c83e96b4fa828b}, doi = {10.1016/j.aml.2009.02.005}, issn = {0893-9659}, keywords = {COMMUNE, clustering, community, detection, spectral}, abstract = {Exploring recent developments in spectral clustering, we discovered that relaxing a spectral reformulation of Newman's Q-measure (a measure that may guide the search for-and help to evaluate the fit of - community structures in networks) yields a new framework for use in detecting fuzzy communities and identifying so-called unstable nodes. In this note, we present and illustrate this approach, which we expect to further enhance our understanding of the intrinsic structure of networks and of network-based clustering procedures. We applied a variation of the fuzzy k-means algorithm, an instance of our framework, to two social networks. The computational results illustrate its potential.} }

%0 = article %A = Jiang, Jeffrey Q. and Dress, Andreas W.M. and Yang, Genke %D = 2009 %T = A spectral clustering-based framework for detecting community structures in complex networks %U = http://www.sciencedirect.com/science/article/B6TY9-4W6XYH5-5/2/693a9ed19784792496c83e96b4fa828b

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

@article{brandes2008modularity, author = {Brandes, U. and Delling, D. and Gaertler, M. and Gorke, R. and Hoefer, M. and Nikoloski, Z. and Wagner, D.}, title = {On Modularity Clustering}, journal = {Knowledge and Data Engineering, IEEE Transactions on}, year = {2008}, volume = {20}, number = {2}, pages = {172 -188}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4358966&tag=1}, doi = {10.1109/TKDE.2007.190689}, issn = {1041-4347}, keywords = {COMMUNE, clustering, community, detection, modularity}, abstract = {Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.} }

%0 = article %A = Brandes, U. and Delling, D. and Gaertler, M. and Gorke, R. and Hoefer, M. and Nikoloski, Z. and Wagner, D. %D = 2008 %T = On Modularity Clustering %U = http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4358966&tag=1

@article{PhysRevLett.100.118703, author = {Leicht, E. A. and Newman, M. E. J.}, title = {Community Structure in Directed Networks}, journal = {Phys. Rev. Lett.}, publisher = {American Physical Society}, year = {2008}, volume = {100}, number = {11}, pages = {118703}, url = {http://prl.aps.org/abstract/PRL/v100/i11/e118703}, doi = {10.1103/PhysRevLett.100.118703}, keywords = {COMMUNE, community, detection, directed, graph, network, structure} }

%0 = article %A = Leicht, E. A. and Newman, M. E. J. %D = 2008 %I = American Physical Society %T = Community Structure in Directed Networks %U = http://prl.aps.org/abstract/PRL/v100/i11/e118703

Complex networks topologies present interesting and surprising properties,
ch as community structures, which can be exploited to optimize communication,
find new efficient and context-aware routing algorithms or simply to
derstand the dynamics and meaning of relationships among nodes. Complex
tworks are gaining more and more importance as a reference model and are a
werful interpretation tool for many different kinds of natural, biological
d social networks, where directed relationships and contextual belonging of
des to many different communities is a matter of fact. This paper starts from
e definition of modularity function, given by M. Newman to evaluate the
odness of network community decompositions, and extends it to the more
neral case of directed graphs with overlapping community structures.
teresting properties of the proposed extension are discussed, a method for
nding overlapping communities is proposed and results of its application to
nchmark case-studies are reported. We also propose a new dataset which could
used as a reference benchmark for overlapping community structures
entification.

@misc{Nicosia2008, author = {Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M.}, title = {Extending the definition of modularity to directed graphs with
overlapping communities}, year = {2008}, note = {cite arxiv:0801.1647
mment: 22 pages, 11 figures}, url = {http://arxiv.org/abs/0801.1647}, keywords = {COMMUNE, community, directed, graph, modularity, network, overlapping}, abstract = { Complex networks topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of modularity function, given by M. Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new dataset which could be used as a reference benchmark for overlapping community structures identification. } }

%0 = misc %A = Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M. %B = } %C = %D = 2008 %I = %T = Extending the definition of modularity to directed graphs with
overlapping communities} %U = http://arxiv.org/abs/0801.1647

@article{PhysRevE.70.056131, author = {Newman, M. E. J.}, title = {Analysis of weighted networks}, journal = {Phys. Rev. E}, publisher = {American Physical Society}, year = {2004}, volume = {70}, number = {5}, pages = {056131}, url = {http://pre.aps.org/abstract/PRE/v70/i5/e056131}, doi = {10.1103/PhysRevE.70.056131}, keywords = {COMMUNE, community, detection, graphs, modularity, networks, weighted} }

%0 = article %A = Newman, M. E. J. %D = 2004 %I = American Physical Society %T = Analysis of weighted networks %U = http://pre.aps.org/abstract/PRE/v70/i5/e056131

Conceptual clustering is an important way of summarizing and explaining data. However, the recent formulation of this paradigm has allowed little exploration of conceptual clustering as a means of improving performance. Furthermore, previous work in conceptual clustering has not explicitly dealt with constraints imposed by real world environments. This article presents COBWEB, a conceptual clustering system that organizes data so as to maximize inference ability. Additionally, COBWEB is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
-

@article{h1987knowledge, author = {Fisher, Douglas H.}, title = {Knowledge Acquisition Via Incremental Conceptual Clustering}, journal = {Machine Learning}, year = {1987}, volume = {2}, number = {2}, pages = {139--172}, url = {http://dx.doi.org/10.1023/A:1022852608280}, keywords = {COMMUNE, classit, clustering, community, coweb, detection}, abstract = {Conceptual clustering is an important way of summarizing and explaining data. However, the recent formulation of this paradigm has allowed little exploration of conceptual clustering as a means of improving performance. Furthermore, previous work in conceptual clustering has not explicitly dealt with constraints imposed by real world environments. This article presents COBWEB, a conceptual clustering system that organizes data so as to maximize inference ability. Additionally, COBWEB is incremental and computationally economical, and thus can be flexibly applied in a variety of domains. ER -} }

%0 = article %A = Fisher, Douglas H. %D = 1987 %T = Knowledge Acquisition Via Incremental Conceptual Clustering %U = http://dx.doi.org/10.1023/A:1022852608280