ganden's community [15 articles]

Abstract

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

Abstract

本研究では，成長する複雑ネットワークの一例としてWeb 上のブログのネットワークを扱い，効率的な情報抽出のためのコミュニティ分割手法の比較検討を行う．まず，既存のコミュニティ分割手法を動的に変化するネットワークに対して適用し，各分割手法を分割コミュニティのモジュール度(Modularity) と安定度(Stability) の観点から評価する．様々なネットワークトポロジと，それに対する各コミュニティ分割手法の振る舞いを観察し，得られた知見をもとにブログネットワークに適したコミュニティ分割手法を考察する． ...

Abstract

本研究では，これまで静的なネットワークを対象としてきたコミュニティ分割手法を成長する複雑ネットワークに対して適用し，得られる分割コミュニティの構造変化の様子から，既存手法がどのように作用するかを観察するための方法論を提案する．その際，2 つの新たな指標を用いてコミュニティ分割手法の安定度，ならびに分割コミュニティに基づいたノードの安定度を定量化し，理論モデルから生成した成長ネットワークを対象とした実験を通してそれらの特徴を明らかにする．Recently, many studies have been made on complex networks and finding their community by means of dividing them based on their network topology. However these studies usually are interested in static networks rather than evolving one. In this paper, we propose how to evaluate stability of community structure and vertex in community for each existing dividing method. Then, we run a computer simulation and come out characteristics of that’s evaluation score of stability. ...

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

Abstract

ommunity detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization ...

Abstract

Structurally segregated and functionally specialized regions of the human cerebral cortex are interconnected by a dense network of cortico-cortical axonal pathways. By using diffusion spectrum imaging, we noninvasively mapped these pathways within and across cortical hemispheres in individual human participants. An analysis of the resulting large-scale structural brain networks reveals a structural core within posterior medial and parietal cerebral cortex, as well as several distinct temporal and frontal modules. Brain regions within the structural core share high degree, strength, and betweenness ...

Abstract

Social networking sites (SNS) have recently used by millions of people all over the world. An SNS is a society on the Internet, where people communicate and foster friendship with each other. We examine a nation-wide SNS (more than six million users at present), mutually acknowledged friendship network with third million people and nearly two million links. By employing a community-extracting method developed by Newman and others, we found that there exists a range of community-sizes in which only few communities are detected. This novel feature cannot be ...

Abstract

Two natural and widely used representations for the community structure of networks are clusterings, which partition the vertex set into disjoint subsets, and layouts, which assign the vertices to positions in a metric space. This paper unifies prominent characterizations of layout quality and clustering quality, by showing that energy models of pairwise attraction and repulsion subsume Newman and Girvan's modularity measure. Layouts with optimal energy are relaxations of, and are thus consistent with, clusterings with optimal modularity, which is of practical relevance because both representations are complementary and often ...

Abstract

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper propose an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to ...

Abstract

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are ...

Abstract

We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph ...

Abstract

Many naturally-occurring networks share topological characteristics such as scale-free connectivity and a modular organization. It has recently been suggested that a hierarchically modular organization may be another such ubiquitous characteristic. In this paper we introduce a coherence metric for the quantification of structural modularity, and use this metric to demonstrate that a self-organized social network derived from Internet Relay Chat (IRC) channel interactions exhibits measurable hierarchical modularity, reflecting an underlying hierarchical neighbourhood structure in the social network. ...

Abstract

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that 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 ...

Abstract

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

Abstract

The rich set of interactions between individuals in society1, 2, 3, 4, 5, 6, 7 results in complex community structure, capturing highly connected circles of friends, families or professional cliques in a social network3, 7, 8, 9, 10. Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution7, 11, 12, 13, 14, 15, 16. Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is ...