CiteULike: fukken's library [37 articles]

Detecting Fuzzy Community Structures in Complex Networks with a Potts Model

Jörg Reichardt — 2007-09-03T05:02:40-00:00

Physical Review Letters, Vol. 93, No. 21. (2004)

A fast community detection algorithm based on a q-state Potts model is presented. Communities (groups of densely interconnected nodes that are only loosely connected to the rest of the network) are found to coincide with the domains of equal spin value in the minima of a modified Potts spin glass Hamiltonian. Comparing global and local minima of the Hamiltonian allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community. No prior knowledge of the number of communities has to be assumed.

Fuzzy clustering for categorical multivariate data

Chi-Hyon Oh — 2007-07-05T06:06:01-00:00

IFSA World Congress and 20th NAFIPS International Conference, 2001. Joint 9th, Vol. 4 (2001), pp. 2154-2159 vol.4.

This paper proposes a new fuzzy clustering algorithm for categorical multivariate data. The conventional fuzzy clustering algorithms form fuzzy clusters so as to minimize the total distance from cluster centers to data points. However, they cannot be applied to the case where only cooccurrence relations among individuals and categories are given and the criterion to obtain clusters is not available. The proposed method enables us to handle that kind of data set by maximizing the degree of aggregation among clusters. The clustering results by the proposed method show similarity to those of correspondence analysis or Hayashi's (1952) quantification method Type III. Numerical examples show the usefulness of our method

Module identification in bipartite networks with applications to directed networks

R Guimera — 2007-07-05T05:13:01-00:00

(12 Jan 2007)

Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in an important class of networks known as bipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. We suggest a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that permit the evaluation of the accuracy of the new approach. Finally, we discuss how our approach can also be used to accurately identify modules in directed unipartite networks.

Fuzzy Co-clustering of Web Documents

William-Chandra Tjhi — 2007-03-18T21:00:14-00:00

(2005), pp. 545-551.

Fuzzy co-clustering of documents and keywords

K Kummamuru — 2007-03-02T03:15:46-00:00

Fuzzy Systems, 2003. FUZZ '03. The 12th IEEE International Conference on, Vol. 2 (2003), pp. 772-777 vol.2.

Conventional clustering algorithms such as K-means and SAHN (also known as AHC) have been well studied and used in the information retrieval community for clustering text documents. More recently, efforts have been made to cluster documents and words simultaneously. The FCCM algorithm due to Oh et al. is a fuzzy clustering algorithm that maximizes the co-occurrence of categorical attributes (keywords) and the individual patterns (documents) in clusters. However, this algorithm poses certain problems when the number of documents or the number of words is very large. In this paper, we modify the FCCM algorithm so that it can be used to cluster large text corpora. Our experiments show that the modified algorithm is scalable and produces meaningful clusters. We also show the relation between FCCM and the Spherical K-Means (SKM) algorithm and introduce the Spherical Fuzzy c-Means (SFCM) algorithm.

Evaluating collaborative filtering recommender systems

Jonathan Herlocker — 2005-04-27T17:40:41-00:00

ACM Trans. Inf. Syst., Vol. 22, No. 1. (January 2004), pp. 5-53.

Random graphs with arbitrary degree distributions and their applications

MEJ Newman — 2007-07-04T09:03:27-00:00

(7 May 2001)

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Co-clustering documents and words using bipartite spectral graph partitioning

Inderjit Dhillon — 2007-03-17T06:02:05-00:00

(2001), pp. 269-274.

Document clustering using word clusters via the information bottleneck method

Noam Slonim — 2005-11-28T03:41:46-00:00

(2000), pp. 208-215.

Subspace clustering for high dimensional data: a review

Lance Parsons — 2005-09-22T04:58:48-00:00

SIGKDD Explor. Newsl., Vol. 6, No. 1. (June 2004), pp. 90-105.

Bipartite graph partitioning and data clustering

Hongyuan Zha — 2006-04-30T15:04:00-00:00

(2001), pp. 25-32.

GroupLens: an open architecture for collaborative filtering of netnews

Paul Resnick — 2005-04-25T21:38:25-00:00

(1994), pp. 175-186.

Local method for detecting communities

James Bagrow — 2006-09-29T06:28:21-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 72, No. 4. (2005)

We propose a method of community detection that is computationally inexpensive and possesses physical significance to a member of a social network. This method is unlike many divisive and agglomerative techniques and is local in the sense that a community can be detected within a network without requiring knowledge of the entire network. A global application of this method is also introduced. Several artificial and real-world networks, including the famous Zachary karate club, are analyzed.

Dynamical clustering methods to find community structures

S Boccaletti — 2006-09-27T08:43:17-00:00

(20 Jul 2006)

We introduce an efficient method for the detection and identification of community structures in complex networks, based on the cluster de-synchronization properties of phase oscillators. The performance of the algorithm is tested on computer generated and real-world networks whose community structure is already known or has been studied by means of other methods. The algorithm attains a high level of precision, especially when the communities are very mixed and hardly detectable by the other methods, with a computational effort $\cal O(KN)$ on a generic graph with $N$ nodes and $K$ links.

Finding community structure in networks using the eigenvectors of matrices

MEJ Newman — 2006-06-07T20:38:54-00:00

(19 May 2006)

We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a new centrality measure that identifies those vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.

Modularity and community structure in networks

MEJ Newman — 2006-06-06T11:38:23-00:00

(17 Feb 2006)

Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.

Fast algorithm for detecting community structure in networks

MEJ Newman — 2005-02-15T17:25:06-00:00

(22 September 2003)

It has been found that many networks display community structure -- groups of vertices within which connections are dense but between which they are sparser -- and highly sensitive computer algorithms have in recent years been developed for detecting such structure. These algorithms however are computationally demanding, which limits their application to small networks. Here we describe a new algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster than previous algorithms. We give several example applications, including one to a collaboration network of more than 50000 physicists.

From the Cover: Modularity and community structure in networks

MEJ Newman — 2006-06-07T05:40:22-00:00

PNAS, Vol. 103, No. 23. (6 June 2006), pp. 8577-8582.

Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as "modularity" over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets. 10.1073/pnas.0601602103

Link prediction approach to collaborative filtering

Zan Huang — 2006-07-13T04:36:13-00:00

(2005), pp. 141-142.

Bipartite structure of all complex networks

Jean-Loup Guillaume — 2006-06-28T07:00:54-00:00

Inf. Process. Lett., Vol. 90, No. 5. (June 2004), pp. 215-221.

Finding and evaluating community structure in networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(11 August 2003)

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 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.

Community structure in social and biological networks

Michelle Girvan — 2005-09-30T09:22:46-00:00

(7 Dec 2001)

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.

Analysis of weighted networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(20 July 2004)

The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a new and simple proof of the max-flow/min-cut theorem.

Item-based collaborative filtering recommendation algorithms

Badrul Sarwar — 2005-11-23T21:38:36-00:00

(2001), pp. 285-295.

Recommender systems apply knowledge discovery techniques to the problem of making personalized recommendations for information, products or services during a live interaction. These systems, especially the k-nearest neighbor collaborative filtering based ones, are achieving widespread success on the Web. The tremendous growth in the amount of available information and the number of visitors to Web sites in recent years poses some key challenges for recommender systems. These are: producing...

Using mixture models for collaborative filtering

Jon Kleinberg — 2005-02-25T22:09:47-00:00

(2004), pp. 569-578.

Joining collaborative and content-based filtering

P Baudisch — 2006-01-30T21:17:44-00:00

Different authors have proposed combining content-based and collaborative attributes in a single table. In this article, we try out a different approach. We propose not to merge the two tables, but to join them as if they were tables in a relational database. As a result, we get several new application cases and a system architecture that supports the formulation of universal queries.

Clustering Methods For Collaborative Filtering

L Ungar — 2006-02-03T17:35:53-00:00

(1998)

Grouping people into clusters based on the items they have purchased allows accurate recommendations of new items for purchase: if you and I have liked many of the same movies, then I will probably enjoy other movies that you like. Recommending items based on similarity of interest (a.k.a. collaborative filtering) is attractive for many domains: books, CDs, movies, etc., but does not always work well. Because data are always sparse -- any given person has seen only a small fraction of all...

Amazon.com Recommendations: Item-to-Item Collaborative Filtering

Greg Linden — 2005-10-10T12:24:34-00:00

IEEE Internet Computing, Vol. 7, No. 1. (January 2003), pp. 76-80.

Why social networks are different from other types of networks

MEJ Newman — 2005-09-30T09:20:29-00:00

(26 May 2003)

We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have non-trivial clustering or network transitivity, and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could account for the observed clustering. We demonstrate that group structure in networks can also account for degree correlations. We show using a simple model that we should expect assortative mixing in such networks whenever there is variation in the sizes of the groups and that the predicted level of assortative mixing compares well with that observed in real-world networks.

Statistical mechanics of complex networks

Reka Albert — 2006-03-18T18:52:14-00:00

Reviews of Modern Physics, Vol. 74, No. 1. (2002)

Complex networks describe a wide range of systems in nature and society. Frequently cited examples include the cell, a network of chemicals linked by chemical reactions, and the Internet, a network of routers and computers connected by physical links. While traditionally these systems have been modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks are governed by robust organizing principles. This article reviews the recent advances in the field of complex networks, focusing on the statistical mechanics of network topology and dynamics. After reviewing the empirical data that motivated the recent interest in networks, the authors discuss the main models and analytical tools, covering random graphs, small-world and scale-free networks, the emerging theory of evolving networks, and the interplay between topology and the network's robustness against failures and attacks.

The structure and function of complex networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(25 March 2003)

Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

The Structure of Collaborative Tagging Systems

Scott Golder — 2005-08-27T17:06:09-00:00

(18 Aug 2005)

Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge.

Piggy Bank: Experience the Semantic Web Inside Your Web Browser

D Huynh — 2006-04-20T14:58:43-00:00

(2005)

Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions

G Adomavicius — 2005-04-26T12:49:12-00:00

Knowledge and Data Engineering, IEEE Transactions on, Vol. 17, No. 6. (2005), pp. 734-749.

This paper presents an overview of the field of recommender systems and describes the current generation of recommendation methods that are usually classified into the following three main categories: content-based, collaborative, and hybrid recommendation approaches. This paper also describes various limitations of current recommendation methods and discusses possible extensions that can improve recommendation capabilities and make recommender systems applicable to an even broader range of applications. These extensions include, among others, an improvement of understanding of users and items, incorporation of the contextual information into the recommendation process, support for multcriteria ratings, and a provision of more flexible and less intrusive types of recommendations.

Model-based User Interface Design

H Trtteberg — 2005-11-27T21:50:09-00:00

(2001)

This work is about supporting user interface design by means of explicit design representations, in particular models.

Social network analysis: An approach and technique for the study of information exchange

Caroline Haythornthwaite — 2006-04-26T02:43:14-00:00

Library & Information Science Research, Vol. 18, No. 4. ( 1996), pp. 323-342.

Social network analysis is an approach and set of techniques used to study the exchange of resources among actors (i.e., individuals, groups, or organizations). One such resource is information. Regular patterns of information exchange reveal themselves as social networks, with actors as nodes in the network and information exchange relationships as connectors between nodes. Just as roads structure the flow of resources among cities, information exchange relationships structure the flow of information among actors. Social network analysis assesses information opportunities for individuals or groups of individuals in terms of exposure to and control of information. By gaining awareness of existing information exchange routes, information providers can act on information opportunities and make changes to information routes to improve the delivery of information services.

Diffusion on Complex Networks : A way to probe their large scale topological structures

Ingve Simonsen — 2004-11-22T00:17:30-00:00

(18 December 2003)

A diffusion process on complex networks is introduced in order to uncover their large scale topological structures. This is achieved by focusing on the slowest decaying diffusive modes of the network. The proposed procedure is applied to real-world networks like a friendship network of known modular structure, and an Internet routing network. For the friendship network, its known structure is well reproduced. In case of the Internet, where the structure is far less well-known, one indeed finds a modular structure, and modules can roughly be associated with individual countries. Quantitatively the modular structure of the Internet manifests itself in an approximately 10 times larger participation ratio of its slowest decaying modes as compared to the null model -- a random scale-free network. The extreme edges of the Internet are found to correspond to Russian and US military sites.