The communities of a social network are sets of vertices with more connections inside the set than outside. We theoretically demonstrate that two commonly observed properties of social networks, heavy-tailed degree distributions and large clustering coefficients, imply the existence of vertex neighborhoods (also known as egonets) that are themselves good communities. We evaluate these neighborhood communities on a range of graphs. What we find is that the neighborhood communities often exhibit conductance scores that are as good as the Fiedler cut. Also, the conductance of neighborhood communities shows similar behavior as the network community profile computed with a personalized PageRank community detection method. The latter requires sweeping over a great many starting vertices, which can be expensive. By using a small and easy-to-compute set of neighborhood communities as seeds for these PageRank communities, however, we find communities that precisely capture the behavior of the network community profile when seeded everywhere in the graph, and at a significant reduction in total work.
Predictable behavior in the structure of ego-nets makes them a useful tool for detecting anomalous patterns in the structure of the network. For instance, Akoglu et al. @cite_38 compute a small collection of measures on each egonet, such as the average degree and largest eigenvalues. Outliers in this space of vertices are often rather anomalous vertices. Our work is, in contrast, a precise statement about the regularity of the ego-nets, and says that we always expect a large ego-net to be a good community.
@cite_38
2075861172 2065153599 2164210932 2169404653
In this paper we investigate the problem of detecting small and subtle subgraphs embedded into a large graph with a common structure. We call the embedded small and subtle subgraphs as signals or anomalies and the large graph as background. Those small and subtle signals, which are structurally dissimilar to the background, are often hidden within graph communities and cannot be revealed in the graph's global structure. We explore the minor eigenvectors of the graph's adjacency matrix to detect subtle anomalies from a background graph. We demonstrate that when there are such subtle anomalies, there exist some minor eigenvectors with extreme values on some entries corresponding to the anomalies. Under the assumption of the Erdos---Renyi random graph model, we derive the formula that show how eigenvector entries are changed and give detectability conditions. We then extend our theoretical study to the general case where multiple anomalies are embedded in a background graph with community structure. We develop an algorithm that uses the eigenvector kurtosis to filter out the eigenvectors that capture the signals. Our theoretical analysis and empirical evaluations on both synthetic data and real social networks show effectiveness of our approach to detecting subtle signals. Recent work has demonstrated that many social networks, and indeed many networks of other types also, have broad distributions of vertex degree. Here we show that this has a substantial impact on the shape of ego-centered networks, i.e., sets of network vertices that are within a given distance of a specified central vertex, the ego. This in turn affects concepts and methods based on ego-centered networks, such as snowball sampling and the Oripple effect.O In particular, we argue that oneOs acquaintances, oneOs immediate neighbors in the acquaintance network, are far from being a random sample of the population, and that this biases the numbers of neighbors two and more steps away. We demonstrate this concept using data drawn from academic collaboration networks, for which, as we show, current simple theories for the typical size of ego-centered networks give numbers that differ greatly from those measured in reality. We present an improved theoretical model which gives significantly better results. The increasing practicality of large-scale flow capture makes it possible to conceive of traffic analysis methods that detect and identify a large and diverse set of anomalies. However the challenge of effectively analyzing this massive data source for anomaly diagnosis is as yet unmet. We argue that the distributions of packet features (IP addresses and ports) observed in flow traces reveals both the presence and the structure of a wide range of anomalies. Using entropy as a summarization tool, we show that the analysis of feature distributions leads to significant advances on two fronts: (1) it enables highly sensitive detection of a wide range of anomalies, augmenting detections by volume-based methods, and (2) it enables automatic classification of anomalies via unsupervised learning. We show that using feature distributions, anomalies naturally fall into distinct and meaningful clusters. These clusters can be used to automatically classify anomalies and to uncover new anomaly types. We validate our claims on data from two backbone networks (Abilene and Geant) and conclude that feature distributions show promise as a key element of a fairly general network anomaly diagnosis framework. There has been a quickly growing interest in networks, since they can represent the structure of a wide class of complex systems occurring from the level of cells to society. Data obtained on real networks show that the corresponding graphs exhibit unexpected nontrivial properties, e.g., anomalous degree distributions, diameter, spreading phenomena, clustering coefficient, and correlations [1]. Very recently great attention has been paid to the local structural units of networks. Small and well defined subgraphs have been introduced as ‘‘motifs’’ [2]. Their distribution and clustering properties [2,3] can be used to interpret global features as well. Somewhat larger units, made up of vertices that are more densely connected to each other than to the rest of the network, are often referred to as communities [4], and have been considered to be the essential structural units of real networks. They have no obvious definition, and most of the recent methods for their identification rely on dividing the network into smaller pieces. The biggest drawback of these methods is that they do not allow for overlapping communities, although overlaps are generally assumed to be crucial features of communities. In this Letter we lay down the fundamentals of a kind of percolation phenomenon on graphs, which can also be used as an effective and deterministic method for uniquely identifying overlapping communities in large real networks [5]. Meanwhile, the various aspects of the classical Erdo ýs