The default approach to deal with the enormous size and limited accessibility of many Web and social media networks is to sample one or more subnetworks from a conceptually unbounded unknown network. Clearly, the extracted subnetworks will crucially depend on the sampling scheme. Motivated by studies of homophily and opinion formation, we propose a variant of snowball sampling designed to prioritize the inclusion of entire cohesive communities rather than any kind of representativeness, breadth, or depth of coverage. The method is illustrated on a concrete example, and experiments on synthetic networks suggest that it behaves as desired.

We report on computational experiments testing the robustness of scale-free networks. The stylized fact that such networks are robust under random failure but sensitive to targeted attack originates from experiments on instances generated by preferential attachment. We find that these are not representative but rather outliers: they are significantly more fragile under targeted attack than random scale-free networks with the exact same degree sequence. To show that they are, however, not extreme in this respect, we also present two generators producing scale-free networks with the same degree sequence that are even more fragile than the corresponding preferential-attachment networks or more robust than even random graphs. Additionally, we present a new result on Hamiltonian realizability of scaling degree sequences.

We propose a novel formalization of roles in social networks that unifies the most commonly used definitions of role equivalence. As one consequence, we obtain a single, straightforward proof that role equivalences form lattices. Our formalization focuses on the evolution of roles from arbitrary initial conditions and thereby generalizes notions of relative and iterated roles that have been suggested previously. In addition to the unified structure result this provides a micro-foundation for the emergence of roles. Considering the genesis of roles may explain, and help overcome, the problem that social networks rarely exhibit interesting role equivalences of the traditional kind. Finally, we hint at ways to further generalize the role concept to multivariate networks.

Understanding the movement patterns of collectives, such as flocks of birds or fish swarms, is an interesting open research question. The collectives are driven by mutual objectives or react to individual direction changes and external influence factors and stimuli. The challenge in visualizing collective movement data is to show space and time of hundreds of movements at the same time to enable the detection of spatiotemporal patterns. In this paper, we propose MotionRugs, a novel space efficient technique for visualizing moving groups of entities. Building upon established space-partitioning strategies, our approach reduces the spatial dimensions in each time step to a one-dimensional ordered representation of the individual entities. By design, MotionRugs provides an overlap-free, compact overview of the development of group movements over time and thus, enables analysts to visually identify and explore group-specific temporal patterns. We demonstrate the usefulness of our approach in the field of fish swarm analysis and report on initial feedback of domain experts from the field of collective behavior.

Abstract The visualization community has developed to date many intuitions and understandings of how to judge thequalityof views in visualizing data. The computation of a visualization's quality and usefulness ranges from measuring clutter and overlap, up to the existence and perception of specific (visual) patterns. This survey attempts to report, categorize and unify the diverse understandings and aims to establish a common vocabulary that will enable a wide audience to understand their differences and subtleties. For this purpose, we present a commonly applicable quality metric formalization that should detail and relate all constituting parts of a quality metric. We organize our corpus of reviewed research papers along the data types established in the information visualization community: multi‐ and high‐dimensional, relational, sequential, geospatial and text data. For each data type, we select the visualization subdomains in which quality metrics are an active research field and report their findings, reason on the underlying concepts, describe goals and outline the constraints and requirements. One central goal of this survey is to provide guidance on future research opportunities for the field and outline how different visualization communities could benefit from each other by applying or transferring knowledge to their respective subdomain. Additionally, we aim to motivate the visualization community to compare computed measures to the perception of humans.

Abstract Given a set of rectangles embedded in the plane, we consider the problem of adjusting the layout to remove all overlap while preserving the orthogonal order of the rectangles. The objective is to minimize the displacement of the rectangles. We call this problem Minimum-Displacement Overlap Removal (mdor). Our interest in this problem is motivated by the application of displaying metadata of archaeological sites. Because most existing overlap removal algorithms are not designed to minimize displacement while preserving orthogonal order, we present and compare several approaches which are tailored to our particular usecase. We introduce a new overlap removal heuristic which we call reArrange. Although conceptually simple, it is very effective in removing the overlap while keeping the displacement small. Furthermore, we propose an additional procedure to repair the orthogonal order after every iteration, with which we extend both our new heuristic and PRISM, a widely used overlap removal algorithm. We compare the performance of both approaches with and without this order repair method. The experimental results indicate that reArrange is very effective for heterogeneous input data where the overlap is concentrated in few dense regions.

We present a novel uncertain network visualization technique based on node-link diagrams. Nodes expand spatially in our probabilistic graph layout, depending on the underlying probability distributions of edges. The visualization is created by computing a two-dimensional graph embedding that combines samples from the probabilistic graph. A Monte Carlo process is used to decompose a probabilistic graph into its possible instances and to continue with our graph layout technique. Splatting and edge bundling are used to visualize point clouds and network topology. The results provide insights into probability distributions for the entire network-not only for individual nodes and edges. We validate our approach using three data sets that represent a wide range of network types: synthetic data, protein-protein interactions from the STRING database, and travel times extracted from Google Maps. Our approach reveals general limitations of the force-directed layout and allows the user to recognize that some nodes of the graph are at a specific position just by chance.

While privacy preserving mechanisms, such as hiding one's friends list, may be available to withhold personal information on online social networking sites, it is not obvious whether to which degree a user's social behavior renders such an attempt futile. In this paper, we study the impact of additional interaction information on the inference of links between nodes in partially covert networks. This investigation is based on the assumption that interaction might be a proxy for connectivity patterns in online social networks. For this purpose, we use data collected from 586 Facebook profiles consisting of friendship ties (conceptualized as the network) and comments on wall posts (serving as interaction information) by a total of 64 000 users. The link-inference problem is formulated as a binary classification problem using a comprehensive set of features and multiple supervised learning algorithms. Our results suggest that interactions reiterate the information contained in friendship ties sufficiently well to serve as a proxy when the majority of a network is unobserved.

Small-world networks have characteristically low pairwise shortest-path distances, causing distance-based layout methods to generate hairball drawings. Recent approaches thus aim at finding a sparser representation of the graph to amplify variations in pairwise distances. Since the effect of sparsification on the layout is difficult to describe analytically, the incorporated filtering parameters of these approaches typically have to be selected manually and individually for each input instance. We here propose the use of graph invariants to determine suitable parameters automatically. This allows us to perform adaptive filtering to obtain drawings in which the cluster structure is most prominent. The approach is based on an empirical relationship between input and output characteristics that is derived from real and synthetic networks.Experimental evaluation shows the effectiveness of our approach and suggests that it can be used by default to increase the robustness of force-directed layout methods.

The papers in this special section present extended versions of four selected papers from the 2014 IEEE Pacific Visualization Symposium (PacificVis’14).

We show that most algorithms from the literature on listing the triangles of a graph have a common abstraction. Our unifying framework highlights that these seemingly different algorithms are in fact instantiations of a single generic procedure, and even suggests some additional variants. More importantly, it yields parsimonious implementations that are in general more efficient than those described in the original works. In addition, we show that the running time of nearly every triangle listing variant is in (a(G)m), where a(G) is the arboricity of the graph and m the number of edges. So far this bound has been proven only for Chiba and Nishizeki's (SIAM J. Computing, 1985) triangle listing algorithm. Finally, algorithmic experimentation reveals that an improved implementation of this algorithm outperforms all subsequently proposed algorithms.

This contribution points out directions for visualization research in the context of a particular approach to visual analytics. This approach is characterized by a holistic view of the data and its integrated visual representation, and its main requirements are multivariate micro-visualizations, layered abstractions, and direct-response interaction with information-oriented controls.

Empirical social networks are often aggregate proxies for several heterogeneous relations. In online social networks, for instance, interactions related to friendship, kinship, business, interests, and other relationships may all be represented as catchall "friendships." Because several relations are mingled into one, the resulting networks exhibit relatively high and uniform density. As a consequence, the variation in positional differences and local cohesion may be too small for reliable analysis.

State-of-the-art link prediction utilizes combinations of complex features derived from network panel data. We here show that computationally less expensive features can achieve the same performance in the common scenario in which the data is available as a sequence of interactions. Our features are based on social vector clocks, an adaptation of the vector-clock concept introduced in distributed computing to social interaction networks. In fact, our experiments suggest that by taking into account the order and spacing of interactions, social vector clocks exploit different aspects of link formation so that their combination with previous approaches yields the most accurate predictor to date.

Abstract We propose a general technique to visualize multivariate data sequences. It is based on a symbiotic combination of three powerful concepts from information visualization: sparklines, glyphs and gestalt theory. By visualizing several well‐known data sets in new ways we first demonstrate how explicit consideration of gestalt principles can be used to leverage visual perception capabilities for the identification of patterns such as trends, periodicities, change points, or outliers. A more detailed case study with complex and noisy data from a psychological experiment then demonstrates how basic design ideas for gestaltlines can be applied in less controlled, and thus more realistic, situations. The case study is complemented with reports on feedback from domain experts and a user study, both indicating that gestaltlines can be a convenient and valid means to explore and communicate patterns in micro‐visualizations.

Abstract Voronoi treemaps represent hierarchies as nested polygons. We here show that, contrary to the apparent popular belief, utilization of an algorithm for weighted Voronoi diagrams is not only feasible, but also more efficient than previous low‐resolution approximations, even when the latter are implemented on graphics hardware. More precisely, we propose an instantiation of Lloyd's method for centroidal Voronoi diagrams with Aurenhammer's algorithm for power diagrams that yields an algorithm running in 𝒪(n log n) rather than Ω(n2) time per iteration, with n the number of sites. We describe its implementation and present evidence that it is faster also in practice.

We propose a method to highlight query hits in hierarchically clustered collections of interrelated items such as digital libraries or knowledge bases. The method is based on the idea that organizing search results similarly to their arrangement on a fixed reference map facilitates orientation and assessment by preserving a user's mental map. Here, the reference map is built from an MDS layout of the items in a Voronoi treemap representing their hierarchical clustering, and we use techniques from dynamic graph layout to align query results with the map. The approach is illustrated on an archive of newspaper articles.

We propose a technique that allows straight-line graph drawings to be rendered interactively with adjustable level of detail. The approach consists of a novel combination of edge cumulation with density-based node aggregation and is designed to exploit common graphics hardware for speed. It operates directly on graph data and does not require precomputed hierarchies or meshes. As proof of concept, we present an implementation that scales to graphs with millions of nodes and edges, and discuss several example applications.

The main algorithmic challenge in network visualization is the placement of nodes. While plenty of layout algorithms have been proposed, the vast majority of information visualization tools appears to utilize (sometimes a variant of) one of two algorithms: the approach of Fruchterman and Reingold or that of Kamada and Kawai. Both are often referred to as force-directed methods, or spring embedders, and praised for their general applicability, high adaptability, and simplicity. I will argue that commonly used implementations and even the approaches themselves are outdated and, in fact, have always been. They should be replaced by variants of multidimensional scaling that display superior results and scalability, and are just as flexible and easy to implement. Some of these statements may actually be backed by evidence.

In modeling and analysis of longitudinal social networks, visual exploration is used in particular to complement and inform other methods. The most common graphical representations for this purpose appear to be animations and small multiples of intermediate states, depending on the type of media available. We present an alternative approach based on matrix representation of gestaltlines (a combination of Tufte's sparklines with glyphs based on gestalt theory). As a result, we obtain static, compact, yet data-rich diagrams that support specifically the exploration of evolving dyadic relations and persistent group structure, although at the expense of cross-sectional network views and indirect linkages.

With few exceptions, statistical analysis of social networks is currently focused on cross-sectional or panel data. On the other hand, automated collection of network-data often produces event data, i.e., data encoding the exact time of interaction between social actors. In this paper we propose models and methods to analyze such networks of dyadic events and to determine the factors that influence the frequency and quality of interaction. We apply our methods to empirical datasets about political conflicts and test several hypotheses concerning reciprocity and structural balance theory.

Almost every application of spreading activation is accompanied by its own set of often heuristic restrictions on the dynamics. We show that in constraint-free scenarios spreading activation would actually yield query-independent results, so that the specific choice of restrictions is not only a pragmatic computational issue, but crucially determines the outcome.

published

We augment schematic maps of transportation systems by superimposing them on street-level maps that are fitted using image warping techniques. While schematic maps are successful in conveying information about lines and connections in a public transportation network, they usually contain little or no detail describing the environment of stations or their embedding in the surrounding area. The annotation of a distorted city map therefore alleviates this deficiency and improves further the usability of schematic transportation maps by merging two different navigational spaces. Our technique for fitting the street map to the schematic map is based on moving least squares in combination with an overlap control technique. We thus obtain an easily readable transportation network map on which we can show all the typical city map features such as rivers, streets, and parks without compromising on the schematization. Furthermore, for the interactive exploration we couple zooming with warping and control over the level of detail in what we call warping zoom.

We propose a method to visually summarize collections of networks on which a clustering of the vertices is given. Our method allows for efficient comparison of individual networks, as well as for visualizing the average composition and structure of a set of networks. As a concrete application we analyze a set of several hundred personal networks of migrants. On the individual level the network images provide visual hints for assessing the mode of acculturation of the respondent. On the population level they show how cultural integration varies with specific characteristics of the migrants such as country of origin, years of residence, or skin color.

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

We consider routing methods for networks when geographic positions of nodes are available. Instead of using the original geographic coordinates, however, we precompute virtual coordinates using a barycentric layout. Combined with simple geometric routing rules, this greatly reduces the lengths of routes and outperforms algorithms working on the original coordinates. Along with experimental results we proof properties such as guaranteed message delivery and worst-case optimality. Our methods apply to static networks in which short routes are important, but memory for full routing tables is not available and the one-time-precomputation is affordable.

We propose a visualization approach for dynamic affiliation networks in which events are characterized by a set of descriptors. It uses a radial ripple metaphor to display the passing of time and conveys relations among the different constituents through appropriate layout. Our method is particularly suitable when assuming an egocentric perspective, and we illustrate it on movie-actor biographies.

We present a method for visual summary of bilateral conflict structures embodied in event data. Such data consists of actors linked by time-stamped events, and may be extracted from various sources such as news reports and dossiers. When analyzing political events, it is of particular importance to be able to recognize conflicts and actors involved in them. By projecting actors into a conflict space, we are able to highlight the main opponents in a series of tens of thousands of events, and provide a graphic overview of the conflict structure. Moreover, our method allows for smooth animation of the dynamics of a conflict.

We introduce a network visualization technique that supports an analytical method applied in the social sciences. Policy network analysis is an approach to study policy making structures, processes, and outcomes, thereby concentrating on relations between policy actors. An important operational concept for the analysis of policy networks is the notion of centrality, i.e., the distinction of actors according to their importance in a relational structure. We integrate this measure in a layout model for networks by mapping structural to geometric centrality. Thus, centrality values and network data can be presented simultaneously and explored interactively.

The computer--aided solution to algorithmic problems is becoming more and more important in various application domains.This is in particular true for computational geometry.For example, geometric problems naturally arise in image processing, computer graphics, and all kinds of computer-aided design, just to mention a few.Even more, the general tendency towards the application of visual aids in virtually all fields of science, technology, and business raises many new, unexpected geometric challenges.A sound mathematical treatment of these problems and a systematic computational study on the resulting algorithms are desirable.However, in practice, there are often obstacles to such an attempt.In this paper, we will systematically discuss our experiences with a few obstacles that occurred in four of our projects and significantly influenced our reasoning on algorithms in each of them.