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, spectral, svd}, 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

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

@article{drineas2004clustering, author = {Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V.}, title = {Clustering large graphs via the singular value decomposition}, journal = {Machine Learning}, publisher = {Springer}, year = {2004}, volume = {56}, number = {1}, pages = {9--33}, url = {http://scholar.google.de/scholar.bib?q=info:gQY9HvWhsJcJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0}, keywords = {clustering, graph, svd, vldb} }

%0 = article %A = Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. %D = 2004 %I = Springer %T = Clustering large graphs via the singular value decomposition %U = http://scholar.google.de/scholar.bib?q=info:gQY9HvWhsJcJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0

@inproceedings{conf/cvpr/KeK04, author = {Ke, Qifa and Kanade, Takeo}, title = {Robust Subspace Clustering by Combined Use of kNND Metric and SVD Algorithm.}, booktitle = {CVPR (2)}, year = {2004}, pages = {592-599}, url = {http://dblp.uni-trier.de/db/conf/cvpr/cvpr2004-2.html#KeK04}, keywords = {clustering, decomposition, eigenvalue, gaussian, subspace, svd} }

%0 = inproceedings %A = Ke, Qifa and Kanade, Takeo %B = CVPR (2) %D = 2004 %T = Robust Subspace Clustering by Combined Use of kNND Metric and SVD Algorithm. %U = http://dblp.uni-trier.de/db/conf/cvpr/cvpr2004-2.html#KeK04

@inproceedings{OsinskiSW04, author = {Osinski, Stanislaw and Stefanowski, Jerzy and Weiss, Dawid}, title = {Lingo: Search Results Clustering Algorithm Based on Singular Value Decomposition}, booktitle = {Intelligent Information Systems}, year = {2004}, pages = {359-368}, keywords = {clustering, lsi, svd, toread} }

%0 = inproceedings %A = Osinski, Stanislaw and Stefanowski, Jerzy and Weiss, Dawid %B = Intelligent Information Systems %D = 2004 %T = Lingo: Search Results Clustering Algorithm Based on Singular Value Decomposition

@inproceedings{DBLP:conf/sigmod/AggarwalY00, author = {Aggarwal, Charu C. and Yu, Philip S.}, title = {Finding Generalized Projected Clusters In High Dimensional Spaces}, editor = {Chen, Weidong and Naughton, Jeffrey F. and Bernstein, Philip A.}, booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on
Management of Data, May 16-18, 2000, Dallas, Texas, USA}, publisher = {ACM}, year = {2000}, pages = {70-81}, isbn = {1-58113-218-2}, keywords = {clustering, svd, projected} }

%0 = inproceedings %A = Aggarwal, Charu C. and Yu, Philip S. %B = Proceedings of the 2000 ACM SIGMOD International Conference on
Management of Data, May 16-18, 2000, Dallas, Texas, USA %D = 2000 %I = ACM %T = Finding Generalized Projected Clusters In High Dimensional Spaces

@unpublished{ranade:sus, author = {Ranade, A.G.}, title = {Some uses of spectral methods}, year = {2000}, keywords = {clustering, graph, spectral, svd, theory} }

%0 = unpublished %A = Ranade, A.G. %D = 2000 %T = Some uses of spectral methods

. The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of contexts on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics,...

@article{kleinberg99authoritative, author = {Kleinberg, Jon M.}, title = {Authoritative sources in a hyperlinked environment}, journal = {Journal of the ACM}, year = {1999}, volume = {46}, number = {5}, pages = {604--632}, url = {http://dx.doi.org/10.1145/324133.324140}, doi = {10.1145/324133.324140}, keywords = {clustering, svd}, abstract = {. The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of contexts on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics,...} }

%0 = article %A = Kleinberg, Jon M. %D = 1999 %T = Authoritative sources in a hyperlinked environment %U = http://dx.doi.org/10.1145/324133.324140

We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By "categorical data," we mean tables with fields that cannot be naturally ordered by a metric -- e.g., the names of producers of automobiles, or the names of products offered by a manufacturer. Our approach is based on an iterative method for assigning and propagating weights on the categorical values in a table; this facilitates a type of similarity measure arising from the cooccurrence of values in the dataset. Our techniques can be studied analytically in terms of certain types of non-linear dynamical systems. We discuss experiments on a variety of tables of synthetic and real data; we find that our iterative methods converge quickly to prominently correlated values of various categorical fields. 1 Introduction Much of the data in databases is categorical: fields in tables whose attributes cannot naturally be ordered as numerical values can. The pro...

@inproceedings{Gibson98clusteringcategorical, author = {Gibson, David and Kleinberg, Jon and Raghavan, Prabhakar}, title = {Clustering Categorical Data: An Approach Based on Dynamical Systems}, year = {1998}, pages = {311--322}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8003}, keywords = {clustering, svd}, abstract = {We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By "categorical data," we mean tables with fields that cannot be naturally ordered by a metric --- e.g., the names of producers of automobiles, or the names of products offered by a manufacturer. Our approach is based on an iterative method for assigning and propagating weights on the categorical values in a table; this facilitates a type of similarity measure arising from the cooccurrence of values in the dataset. Our techniques can be studied analytically in terms of certain types of non-linear dynamical systems. We discuss experiments on a variety of tables of synthetic and real data; we find that our iterative methods converge quickly to prominently correlated values of various categorical fields. 1 Introduction Much of the data in databases is categorical: fields in tables whose attributes cannot naturally be ordered as numerical values can. The pro...} }

%0 = inproceedings %A = Gibson, David and Kleinberg, Jon and Raghavan, Prabhakar %D = 1998 %T = Clustering Categorical Data: An Approach Based on Dynamical Systems %U = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8003

We propose a new algorithm capable of partitioning a set of documents or other samples based on an embedding in a high dimensional Euclidean space (i.e. in which every document is a vector of real numbers). The method is unusual in that it is divisive, as opposed to agglomerative, and operates by repeatedly splitting clusters into smaller clusters. The splits are not based on any distance or similarity measure. The documents are assembled in to a matrix which is very sparse. It is this sparsity that permits the algorithm to be very efficient. The performance of the method is illustrated with a set of text documents obtained from the World Wide Web. Some possible extensions are proposed for further investigation.

@article{Boley97principaldirection, author = {Boley, Daniel}, title = {Principal Direction Divisive Partitioning}, journal = {Data Mining and Knowledge Discovery}, year = {1997}, volume = {2}, pages = {325--344}, keywords = {clustering, community, detection, divisive, svd}, abstract = {We propose a new algorithm capable of partitioning a set of documents or other samples based on an embedding in a high dimensional Euclidean space (i.e. in which every document is a vector of real numbers). The method is unusual in that it is divisive, as opposed to agglomerative, and operates by repeatedly splitting clusters into smaller clusters. The splits are not based on any distance or similarity measure. The documents are assembled in to a matrix which is very sparse. It is this sparsity that permits the algorithm to be very efficient. The performance of the method is illustrated with a set of text documents obtained from the World Wide Web. Some possible extensions are proposed for further investigation.} }

%0 = article %A = Boley, Daniel %D = 1997 %T = Principal Direction Divisive Partitioning

@techreport{berry94using, author = {Berry, Michael W. and Dumais, Susan T. and O'Brien, Gavin W.}, title = {Using Linear Algebra for Intelligent Information Retrieval}, year = {1994}, number = {UT-CS-94-270}, url = {http://citeseer.ist.psu.edu/berry95using.html}, keywords = {clustering, lsi, svd} }

%0 = techreport %A = Berry, Michael W. and Dumais, Susan T. and O'Brien, Gavin W. %D = 1994 %T = Using Linear Algebra for Intelligent Information Retrieval %U = http://citeseer.ist.psu.edu/berry95using.html