Abstract: As network research becomes more sophisticated, it is more common than ever for researchers to
find themselves not studying a single network but needing to analyze sets of networks. An important task when
working with sets of networks is network comparison, developing a similarity or distance measure between
networks so that meaningful comparisons can be drawn. The best means to accomplish this task remains an
open area of research. Here we introduce a new measure to compare networks, the Portrait Divergence, that
is mathematically principled, incorporates the topological characteristics of networks at all structural scales,
and is general-purpose and applicable to all types of networks. An important feature of our measure that
enables many of its useful properties is that it is based on a graph invariant, the network portrait. We test our
measure on both synthetic graphs and real world networks taken from protein interaction data, neuroscience,
and computational social science applications. The Portrait Divergence reveals important characteristics of
multilayer and temporal networks extracted from data.
Abstract: In this paper we derive an updating scheme for calculating some important network statistics such as degree, clustering coefficient, etc., aiming at reduce the amount of computation needed to track the evolving behavior of large networks; and more importantly, to provide efficient methods for potential use of modeling the evolution of networks. Using the updating scheme, the network statistics can be computed and updated easily and much faster than re-calculating each time for large evolving networks. The update formula can also be used to determine which edge/node will lead to the extremal change of network statistics, providing a way of predicting or designing evolution rule of networks.
Abstract: We propose a method for characterizing large complex networks by introducing a new matrix structure, unique for a given network, which encodes structural information; provides useful visualization, even for very large networks; and allows for rigorous statistical comparison between networks. Dynamic processes such as percolation can be visualized using animations. Applications to graph theory are discussed, as are generalizations to weighted networks, real-world network similarity testing, and applicability to the graph isomorphism problem.
Abstract: This article explores the relationship between communities and short cycles in complex networks, based on the fact that nodes more densely connected amongst one another are more likely to be linked through short cycles. By identifying combinations of 3-, 4- and 5-edge-cycles, a subnetwork is obtained which contains only those nodes and links belonging to such cycles, which can then be used to highlight community structure. Examples are shown using a theoretical model (Sznajd networks) and a real-world network (NCAA football).
Abstract: We study the fame distribution of scientists and other social groups as measured by the number of Google hits garnered by individuals in the population. Past studies have found that the fame distribution decays either in power-law [arXiv:cond-mat/0310049] or exponential [Europhys. Lett., 67, (4) 511-516 (2004)] fashion, depending on whether individuals in the social group in question enjoy true fame or not. In our present study we examine critically Google counts as well as the methods of data analysis. While the previous findings are corroborated in our present study, we find that, in most situations, the data available does not allow for sharp conclusions.
Abstract: We propose a novel 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.
Abstract: Following a recent idea, to measure fame by the number of Google hits found in a search on the WWW, we study the relation between fame (Google hits) and merit (number of papers posted on an electronic archive) for a random group of scientists in condensed matter and statistical physics. Our findings show that fame and merit in science are linearly related, and that the probability distribution for a certain level of fame falls off exponentially. This is in sharp contrast with the original findings about WW II ace pilots, for which fame is exponentially related to merit (number of downed planes), and the probability of fame decays in power-law fashion. Other groups in our study show similar patterns of fame as for ace pilots.