Author Archives: bolozna

R. Toivonen, L. Kovanen, M. Kivelä, J.-P. Onnela, J. Saramäki, K. Kaski

This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attributes (nodal attribute models, NAMs). An exponential random graph model (ERGM) with structural dependencies is included for comparison. We fit models from each of these categories to two empirical acquaintance networks with respect to basic network properties. We compare higher order structures in the resulting networks with those in the data, with the aim of determining which models produce the most realistic network structure with respect to degree distributions, assortativity, clustering spectra, geodesic path distributions, and community structure (subgroups with dense internal connections). We find that the nodal attribute models successfully produce assortative networks and very clear community structure. However, they generate unrealistic clustering spectra and peaked degree distributions that do not match empirical data on large social networks. On the other hand, many of the network evolution models produce degree distributions and clustering spectra that agree more closely with data. They also generate assortative networks and community structure, although often not to the same extent as in the data. The ERGM model, which turned out to be near-degenerate in the parameter region best fitting our data, produces the weakest community structure.

Social Networks 31(4), p. 240–254

Read the full text

J. Kumpula, M. Kivelä, K. Kaski, J. Saramäki

In complex network research clique percolation, introduced by Palla, Derényi, and Vicsek [Nature (London) 435, 814 (2005)], is a deterministic community detection method which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This method is based on sequentially inserting the constituent links to the network and simultaneously keeping track of the emerging community structure. Unlike existing algorithms, the SCP method allows for detecting k-clique communities at multiple weight thresholds in a single run, and can simultaneously produce a dendrogram representation of hierarchical community structure. In sparse weighted networks, the SCP algorithm can also be used for implementing the weighted clique percolation method recently introduced by Farkas et al. [New J. Phys. 9, 180 (2007)]. The computational time of the SCP algorithm scales linearly with the number of k-cliques in the network. As an example, the method is applied to a product association network, revealing its nested community structure.

Physical Review E 78, 026109

Read the full text

J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski, J. Kertész

The recent high level of interest in weighted complex networks gives rise to a need to develop new measures and to generalize existing ones to take the weights of links into account. Here we focus on various generalizations of the clustering coefficient, which is one of the central characteristics in the complex network theory. We present a comparative study of the several suggestions introduced in the literature, and point out their advantages and limitations. The concepts are illustrated by simple examples as well as by empirical data of the world trade and weighted coauthorship networks.

Physical Review E 75, 027105

Read the full text