To find interesting structure in networks, community detection algorithms have to take into account not only the network topology, but also dynamics of interactions between nodes. We investigate this claim using the paradigm of synchronization in a network of coupled oscillators. As the network evolves to a global steady state, nodes belonging to the same community synchronize faster than nodes belonging to different communities. Traditionally, nodes in network synchronization models are coupled via one-to-one, or conservative interactions. However, social interactions are often one-to-many, as for example, in social media, where users broadcast messages to all their followers. We formulate a novel model of synchronization in a network of coupled oscillators in which the oscillators are coupled via one-to-many, or non-conservative interactions. We study the dynamics of different interaction models and contrast their spectral properties. To find multi-scale community structure in a network of interacting nodes, we define a similarity function that measures the degree to which nodes are synchronized and use it to hierarchically cluster nodes. We study real-world social networks, including networks of two social media providers. To evaluate the quality of the discovered communities in a social media network we propose a community quality metric based on user activity. We find that conservative and non-conservative interaction models lead to dramatically different views of community structure even within the same network. Our work offers a novel mathematical framework for exploring the relationship between network structure, topology and dynamics.
Community detection methods are used to reveal the structure of complex networks. @cite_5 found core and whiskers' structure of real-world networks using conductance-based methods and argued that these methods cannot reveal any further structure in the giant core. Song @cite_17 claimed that there exist self-repeating patterns in complex networks at all length scales. Our results corroborate this claim, as we show a repeating core and whiskers' pattern in the Digg social network at many different length scales.
@cite_5 @cite_17
2131717044 1973353128
Repetition is a core principle in music. Many musical pieces are characterized by an underlying repeating structure over which varying elements are superimposed. This is especially true for pop songs where a singer often overlays varying vocals on a repeating accompaniment. On this basis, we present the REpeating Pattern Extraction Technique (REPET), a novel and simple approach for separating the repeating “background” from the non-repeating “foreground” in a mixture. The basic idea is to identify the periodically repeating segments in the audio, compare them to a repeating segment model derived from them, and extract the repeating patterns via time-frequency masking. Experiments on data sets of 1,000 song clips and 14 full-track real-world songs showed that this method can be successfully applied for music voice separation, competing with two recent state-of-the-art approaches. Further experiments showed that REPET can also be used as a preprocessor to pitch detection algorithms to improve melody extraction. Real world complex networks are scale free and possess meso-scale properties like core-periphery and community structure. We study evolution of the core over time in real world networks. This paper proposes evolving models for both unweighted and weighted scale free networks having local and global core-periphery as well as community structure. Network evolves using topological growth, self growth, and weight distribution function. To validate the correctness of proposed models, we use K-shell and S-shell decomposition methods. Simulation results show that the generated unweighted networks follow power law degree distribution with droop head and heavy tail. Similarly, generated weighted networks follow degree, strength, and edge-weight power law distributions. We further study other properties of complex networks, such as clustering coefficient, nearest neighbor degree, and strength degree correlation. Understanding of the mechanisms driving our daily face-to-face encounters is still limited; the field lacks large-scale datasets describing both individual behaviors and their collective interactions. However, here, with the help of travel smart card data, we uncover such encounter mechanisms and structures by constructing a time-resolved in-vehicle social encounter network on public buses in a city (about 5 million residents). Using a population scale dataset, we find physical encounters display reproducible temporal patterns, indicating that repeated encounters are regular and identical. On an individual scale, we find that collective regularities dominate distinct encounters’ bounded nature. An individual’s encounter capability is rooted in his her daily behavioral regularity, explaining the emergence of “familiar strangers” in daily life. Strikingly, we find individuals with repeated encounters are not grouped into small communities, but become strongly connected over time, resulting in a large, but imperceptible, small-world contact network or “structure of co-presence” across the whole metropolitan area. Revealing the encounter pattern and identifying this large-scale contact network are crucial to understanding the dynamics in patterns of social acquaintances, collective human behaviors, and—particularly—disclosing the impact of human behavior on various diffusion spreading processes. Networks provide a powerful way to study complex systems of interacting objects. Detecting network communities—groups of objects that often correspond to functional modules—is crucial to understanding social, technological, and biological systems. Revealing communities allows for analysis of system properties that are invisible when considering only individual objects or the entire system, such as the identification of module boundaries and relationships or the classification of objects according to their functional roles. However, in networks where objects can simultaneously belong to multiple modules at once, the decomposition of a network into overlapping communities remains a challenge. Here we present a new paradigm for uncovering the modular structure of complex networks, based on a decomposition of a network into any combination of overlapping, nonoverlapping, and hierarchically organized communities. We demonstrate on a diverse set of networks coming from a wide range of domains that our approach leads to more accurate communities and improved identification of community boundaries. We also unify two fundamental organizing principles of complex networks: the modularity of communities and the commonly observed core–periphery structure. We show that dense network cores form as an intersection of many overlapping communities. We discover that communities in social, information, and food web networks have a single central dominant core while communities in protein–protein interaction (PPI) as well as product copurchasing networks have small overlaps and form many local cores. ‘Scale-free’ networks, such as linked web pages, people in social groups, or cellular interaction networks show uneven connectivity distributions: there is no typical number of links per node. Many of these networks also exhibit the ‘small-world’ effect, called ‘six degrees of separation’ when applied to sociology. A new analysis of such networks, in which nodes are partitioned into boxes of different sizes, reveals that they share the surprising feature of self-similarity. In other words, these networks are constructed of fractal-like self-repeating patterns or degrees of separation. This may help explain how the scale-free property of such networks arises. Recent years have witnessed increased interests in topic detection and tracking (TDT). However, existing work mainly focuses on overall trend analysis, and is not developed for understanding the evolving process of topics. To this end, this paper aims to reveal the underlying process and reasons for topic formation and development (TFD). Along this line, based on community partitioning in social networks, a core-group model is proposed to explain the dynamics and to segment topic development. This model is inspired by the cell division mechanism in biology. Furthermore, according to the division phase and interphase in the life cycle of a core group, a topic is separated into four states including birth state, extending state, saturation state and shrinkage state. In this paper, we mainly focus our studies on scientific topic formation and development using the citation network structure among scientific papers. Experimental results on two real-world data sets show that the division of a core group brings on the generation of a new scientific topic. The results also reveal that the progress of an entire scientific topic is closely correlated to the growth of a core group during its interphase. Finally, we demonstrate the effectiveness of the proposed method in several real-life scenarios. Network data often contain important attributes from various dimensions such as social affiliations and areas of expertise in a social network. If such attributes exhibit a tree structure, visualizing a compound graph consisting of tree and network structures becomes complicated. How to visually reveal patterns of a network over a tree has not been fully studied. In this paper, we propose a compound graph model, TreeNet, to support visualization and analysis of a network at multiple levels of aggregation over a tree. We also present a visualization design, TreeNetViz, to offer the multiscale and cross-scale exploration and interaction of a TreeNet graph. TreeNetViz uses a Radial, Space-Filling (RSF) visualization to represent the tree structure, a circle layout with novel optimization to show aggregated networks derived from TreeNet, and an edge bundling technique to reduce visual complexity. Our circular layout algorithm reduces both total edge-crossings and edge length and also considers hierarchical structure constraints and edge weight in a TreeNet graph. These experiments illustrate that the algorithm can reduce visual cluttering in TreeNet graphs. Our case study also shows that TreeNetViz has the potential to support the analysis of a compound graph by revealing multiscale and cross-scale network patterns. Many researchers have studied complex networks such as the World Wide Web, social networks, and the protein interaction network. They have found scale-free characteristics, the small-world effect, the property of high-clustering coefficient, and so on. One hot topic in this area is community detection. For example, the community shows a set of web pages about a certain topic in the WWW. The community structure is unquestionably a key characteristic of complex networks. In this paper, we propose a new method for finding communities in complex networks. Our proposed method considers the overlaps between communities using the concept of the intersection graph. Additionally, we address the problem of edge in homogeneity by weighting edges using the degree of overlaps and the similarity of content information between sets. Finally, we conduct clustering based on modularity. And then, we evaluate our method on a real SNS network. To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network—including physics, chemistry, molecular biology, and medicine—information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences. Community detection is an important task for mining the structure and function of complex networks. Generally, there are several different kinds of nodes in a network which are cluster nodes densely connected within communities, as well as some special nodes like hubs bridging multiple communities and outliers marginally connected with a community. In addition, it has been shown that there is a hierarchical structure in complex networks with communities embedded within other communities. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm SHRINK by combining the advantages of density-based clustering and modularity optimization methods. Based on the structural connectivity information, the proposed algorithm can effectively reveal the embedded hierarchical community structure with multiresolution in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the sensitive threshold problem of density-based clustering algorithms and the resolution limit possessed by other modularity-based methods. To illustrate our methodology, we conduct experiments with both real-world and synthetic datasets for community detection, and compare with many other baseline methods. Experimental results demonstrate that SHRINK achieves the best performance with consistent improvements. Symmetry in visual data represents repeated patterns or shapes that is easily found in natural and human-made objects. Symmetry pattern on an object works as a salient visual feature attracting human attention and letting the object to be easily recognized. Most existing symmetry detection methods are based on sparsely detected local features describing the appearance of their neighborhood, which have difficulty in capturing object structure mostly supported by edges and contours. In this work, we propose a new reflection symmetry detection method extracting robust 4-dimensional Appearance of Structure descriptors based on a set of outstanding neighbourhood edge segments in multiple scales. Our experimental evaluations on multiple public symmetry detection datasets show promising reflection symmetry detection results on challenging real world and synthetic images. The percolation properties of clustered networks are analyzed in detail. In the case of weak clustering, we present an analytical approach that allows us to find the critical threshold and the size of the giant component. Numerical simulations confirm the accuracy of our results. In more general terms, we show that weak clustering hinders the onset of the giant component whereas strong clustering favors its appearance. This is a direct consequence of the differences in the @math -core structure of the networks, which are found to be totally different depending on the level of clustering. An empirical analysis of a real social network confirms our predictions. We review the recent rapid progress in the statistical physics of evolving networks. Interest has focused mainly on the structural properties of complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of this kind have recently been created, which opens a wide field for the study of their topology, evolution, and the complex processes which occur in them. Such networks possess a rich set of scaling properties. A number of them are scale-free and show striking resilience against random breakdowns. In spite of the large sizes of these networks, the distances between most of their vertices are short - a feature known as the 'small-world' effect. We discuss how growing networks self-organize into scale-free structures, and investigate the role of the mechanism of preferential linking. We consider the topological and structural properties of evolving networks, and percolation and disease spread on these networks. We present a number of models demonstrat... Most community detection algorithms are trying to obtain the global information of the network. But increasingly large scale of the current network makes accessing to global information very difficult. In the meanwhile, the network shows power-law distribution and sparse features. And local community mining algorithms which use these features have more advantages over global mining methods. In this paper, we proposed a local community detection algorithm based on the core members named LLCDA (Leader based Local Community Detecting Algorithm) which uses local structural information in the network to optimize a local objective function. A local community can be detected through continuous optimization of the function by expanding from an initial core member computed by a modified PageRank sorting algorithm. The proposed LLCDA algorithm has been tested on both synthetic and real world networks, and it has been compared with other community detecting algorithms. The experimental results validated our proposed LLCDA and showed that significant improvements have been achieved by this technique. We introduce a computational framework for discovering regular or repeated geometric structures in 3D shapes. We describe and classify possible regular structures and present an effective algorithm for detecting such repeated geometric patterns in point- or meshbased models. Our method assumes no prior knowledge of the geometry or spatial location of the individual elements that define the pattern. Structure discovery is made possible by a careful analysis of pairwise similarity transformations that reveals prominent lattice structures in a suitable model of transformation space. We introduce an optimization method for detecting such uniform grids specifically designed to deal with outliers and missing elements. This yields a robust algorithm that successfully discovers complex regular structures amidst clutter, noise, and missing geometry. The accuracy of the extracted generating transformations is further improved using a novel simultaneous registration method in the spatial domain. We demonstrate the effectiveness of our algorithm on a variety of examples and show applications to compression, model repair, and geometry synthesis. The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems. A new form of document coupling called co-citation is defined as the frequency with which two documents are cited together. The co-citation frequency of two scientific papers can be determined by comparing lists of citing documents in the Science Citation Index and counting identical entries. Networks of co-cited papers can be generated for specific scientific specialties, and an example is drawn from the literature of particle physics. Co-citation patterns are found to differ significantly from bibliographic coupling patterns, but to agree generally with patterns of direct citation. Clusters of co-cited papers provide a new way to study the specialty structure of science. They may provide a new approach to indexing and to the creation of SDI profiles. Networks are widely used in the biological, physical, and social sciences as a concise mathematical representation of the topology of systems of interacting components. Understanding the structure of these networks is one of the outstanding challenges in the study of complex systems. Here we describe a general technique for detecting structural features in large-scale network data that works by dividing the nodes of a network into classes such that the members of each class have similar patterns of connection to other nodes. Using the machinery of probabilistic mixture models and the expectation–maximization algorithm, we show that it is possible to detect, without prior knowledge of what we are looking for, a very broad range of types of structure in networks. We give a number of examples demonstrating how the method can be used to shed light on the properties of real-world networks, including social and information networks. It has long been realized that social network of scientific collaborations provides a window on patterns of collaboration within the academic community. Investigations and studies about static and dynamic properties of co-authorship network have also been done in the recent years. However, the accent of most of the research is on the analysis about the macroscopic structure of the whole network or community over time such as distance, diameter shrinking and densication phenomenon and microscopic formation analysis of links,groups or communities over time. But in fact, how an individual or a community grows over time may not only provide a new view point to mine copious and valuable information about scientific networks but also reveal important factors that influence the growth process. In this paper,from a temporal and microscopic analytical perspective, we propose a method to trace scientific individual's and community's growth process based on community's evolution path combination with quantifiable measurements. During the process of tracing, we find out that it is the fact that the lifespan of community is related to the ability of altering its membership, but what's more and complementary, we find out that the lifespan of community is also related to the ability of maintaining its core members meaning that community may last for a longer lifespan if its core members are much more stable. Meanwhile, we also trace the growth process of research individuals based on the evolution of communities. The proposed survey discusses the topic of community detection in the context of Social Media. Community detection constitutes a significant tool for the analysis of complex networks by enabling the study of mesoscopic structures that are often associated with organizational and functional characteristics of the underlying networks. Community detection has proven to be valuable in a series of domains, e.g. biology, social sciences, bibliometrics. However, despite the unprecedented scale, complexity and the dynamic nature of the networks derived from Social Media data, there has only been limited discussion of community detection in this context. More specifically, there is hardly any discussion on the performance characteristics of community detection methods as well as the exploitation of their results in the context of real-world web mining and information retrieval scenarios. To this end, this survey first frames the concept of community and the problem of community detection in the context of Social Media, and provides a compact classification of existing algorithms based on their methodological principles. The survey places special emphasis on the performance of existing methods in terms of computational complexity and memory requirements. It presents both a theoretical and an experimental comparative discussion of several popular methods. In addition, it discusses the possibility for incremental application of the methods and proposes five strategies for scaling community detection to real-world networks of huge scales. Finally, the survey deals with the interpretation and exploitation of community detection results in the context of intelligent web applications and services.