Graphs are everywhere, growing increasingly complex, and still lack scalable, interactive tools to support sensemaking. To address this problem, we present Atlas, an interactive graph exploration system that adapts scalable edge decomposition to enable a new paradigm for large graph exploration, generating explorable multi-layered representations. Atlas simultaneously reveals peculiar subgraph structures, (e.g., quasi-cliques) and possible vertex roles in connecting such subgraph patterns. Atlas decomposes million-edge graphs in seconds, scaling to graphs with up to 117 million edges. We present the results from a think-aloud user study with three graph experts and highlight discoveries made possible by Atlas when applied to graphs from multiple domains, including suspicious yelp reviews, insider trading, and word embeddings. Atlas runs in-browser and is open-sourced.

Visualization is a powerful paradigm for exploratory data analysis. Visualizing large graphs, however, often results in excessive edges crossings and overlapping nodes. We propose a new scalable approach called Facets that helps users adaptively explore large million-node graphs from a local perspective, guiding them to focus on nodes and neighborhoods that are most subjectively interesting to users. We contribute novel ideas to measure this interestingness in terms of how surprising a neighborhood is given the background distribution, as well as how well it matches what the user has chosen to explore. Facets uses Jensen-Shannon divergence over information-theoretically optimized histograms to calculate the subjective user interest and surprise scores. Participants in a user study found Facets easy to use, easy to learn, and exciting to use. Empirical runtime analyses demonstrated Facets's practical scalability on large real-world graphs with up to 5 million edges, returning results in fewer than 1.5 seconds.

Large dynamic networks are targets of analysis in many fields. Tracking temporal changes at scale in these networks is challenging due in part to the fact that small changes can be missed or drowned-out by the rest of the network. For static networks, current approaches allow the identification of specific network elements within their context. However, in the case of dynamic networks, the user is left alone with finding salient local network elements and tracking them over time. In this work, we introduce a modular DoI specification to flexibly define what salient changes are and to assign them a measure of their importance in a time-varying setting. The specification takes into account neighborhood structure information, numerical attributes of nodes/edges, and their temporal evolution. A tailored visualization of the DoI specification complements our approach. Alongside a traditional node-link view of the dynamic network, it serves as an interface for the interactive definition of a DoI function. By using it to successively refine and investigate the captured details, it supports the analysis of dynamic networks from an initial view until pinpointing a user's analysis goal. We report on applying our approach to scientific coauthorship networks and give concrete results for the DBLP data set.

Degree peeling is used to study complex networks. It corresponds to a decomposition of the graph into vertex groups of increasing minimum degree. However, the peeling value of a vertex is non-local in this context since it relies on the connections the vertex has to groups above it. We explore a different way to decompose a network into edge layers such that the local peeling value of the vertices on each layer does not depend on their non-local connections with the other layers. This corresponds to the decomposition of a graph into subgraphs that are invariant with respect to degree peeling, i.e. they are fixed points. We introduce in this context a method to partition the edges of a graph into fixed points of degree peeling, called the iterative-edge-core decomposition. Information from this decomposition is used to formulate a notion of vertex diversity based on Shannon's entropy. We illustrate the usefulness of this decomposition in social network analysis. Our method can be used for community detection and graph visualization.

We address the problem of detecting characteristic patterns in communication networks. We introduce a scalable approach based on set-system discrepancy. By implicitly labeling each network edge with the sequence of times in which its two endpoints communicate, we view an entire communication network as a set-system. This view allows us to use combinatorial discrepancy as a mechanism to "observe" system behavior at different time scales. We illustrate our approach, called Discrepancy-based Novelty Detector (DND), on networks obtained from emails, blue tooth connections, IP traffic, and tweets. DND has almost linear runtime complexity and linear storage complexity in the number of communications. Examples of novel discrepancies that it detects are (i) asynchronous communications and (ii) disagreements in the firing rates of nodes and edges relative to the communication network as a whole.

We present interactive visual aids to support the exploration and navigation of graph layouts. They include fisheye tree views and composite lenses. These views provide, in an integrated manner, overview+detail and focus+context. Fisheye tree views are novel applications of the well known fisheye distortion technique. They facilitate the exploration of the hierarchy trees associated with clustered graphs. Composite lenses are the result of the integration of several lens techniques. They facilitate the display of local graph information that may be otherwise difficult to grasp in large and dense graph layouts

We describe ASK-GraphView, a node-link-based graph visualization system that allows clustering and interactive navigation of large graphs, ranging in size up to 16 million edges. The system uses a scalable architecture and a series of increasingly sophisticated clustering algorithms to construct a hierarchy on an arbitrary, weighted undirected input graph. By lowering the interactivity requirements we can scale to substantially bigger graphs. The user is allowed to navigate this hierarchy in a top down manner by interactively expanding individual clusters. ASK-GraphView also provides facilities for filtering and coloring, annotation and cluster labeling.

Traffic analysis, in the context of Telecommunications or Internet and Web data, is crucial for large network operations. Data in such networks is often provided as large graphs with hundreds of millions of vertices and edges. We propose efficient techniques for managing such graphs at the storage level in order to facilitate its processing at the interface level(visualization). The methods are based on a hierarchical decomposition of the graph edge set that is inherited from a hierarchical decomposition of the vertex set. Real time navigation is provided by an efficient two level indexing schema called the gkd*-tree. The first level is a variation of a kd-tree index that partitions the edge set in a way that conforms to the hierarchical decomposition and the data distribution (the gkd-tree). The second level is a redundant R-tree that indexes the leaf pages of the gkd-tree. We provide computational results that illustrate the superiority of the gkd-tree against conventional indexes like the kd-tree and the R*-tree both in creation as well as query response times.

An effective way to process a graph that does not fit in RAM is to build a hierarchical partition of its set of vertices. This hierarchy induces a partition of the graph edge set. We use this partition to produce a macro view of the graph. A screen embedding of this macro view is a Graph Sketch. We describe the use of Rectangular FishEye Views to provide drill-down navigation of graph sketches at different levels of detail including the graph edges data. A higher level of detail of a sketch focus area is obtained by distorting the lower detail context. Alternative visual representations can be used at different sketch hierarchy levels. We provide two sketch screen embeddings. One is tree-map based and the other is obtained by a special sequence of graph edge contractions. We demonstrate the application of our current Unix/Windows prototype to telecommunication graphs with edge sets ranging from 100 million to 1 billion edges(Giga-Graphs). To our knowledge this is the first time that focus within context techniques have been used successfully for the navigation of external memory graphs.

Computing the strong components of a directed graph is an essential operation for a basic structural analysis of it. This problem can be solved by twice running a depth-first search (DFS). In an external setting, in which all data can no longer be stored in the main memory, the DFS problem is unsolved so far. Assuming that node-related data can be stored internally, semi-external computing does not make the problem substantially easier. Considering the definite need to analyze very large graphs, we have developed a set of heuristics which together allow the performance of semi-external DFS for directed graphs in practice. The heuristics have been applied to graphs with very different graph properties, including "web graphs" as described in the most recent literature and some large call graphs from ATT. Depending on the graph structure, the program is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.

Describes MGV (Massive Graph Visualizer), an integrated visualization and exploration system for massive multidigraph navigation. It adheres to the visual information-seeking mantra: overview first, zoom and filter, then details on demand. MGV's only assumption is that the vertex set of the underlying digraph corresponds to the set of leaves of a pre-determined tree T. MGV builds an out-of-core graph hierarchy and provides mechanisms to plug in arbitrary visual representations for each graph hierarchy slice. Navigation from one level to another of the hierarchy corresponds to the implementation of a drill-down interface. In order to provide the user with navigation control and interactive response, MGV incorporates a number of visualization techniques like interactive pixel-oriented 2D and 3D maps, statistical displays, color maps, multi-linked views and a zoomable label-based interface. This makes the association of geographic information and graph data very natural. To automate the creation of the vertex set hierarchy for MGV, we use the notion of graph sketches. They can be thought of as visual indices that guide the navigation of a multigraph too large to fit on the available display. MGV follows the client-server paradigm and it is implemented in C and Java-3D. We highlight the main algorithmic and visualization techniques behind the tools and, along the way, point out several possible application scenarios. Our techniques are being applied to multigraphs defined on vertex sets with sizes ranging from 100 million to 250 million vertices.

Chains in the weak Bruhat order$\beta $ of $\text{S}_\Sigma $ (the symmetric group on $\Sigma $) belong to the class of subsets of $\text{S}_\Sigma $ over which unrestricted choice necessarily produces transitive relations under pairwise simple majority vote (consistent sets). If for $\text{A} \subset \text{S}_\Sigma $ we let $\text{T}( \text{A} ) \equiv \cup _{\text{p} \in \text{A}} \text{T} ( \text{p} )$ where $\text{T}( \text{p} ) = \{ ( \text{p}_{\text{i}} , \text{p}_{\text{j}} ,\text{p}_{\text{k}} )| \text{i} < \text{j} < \text{k} \}$ and $\Psi ( \text{A} ) \equiv \{ \text{w} \in \text{S}_\Sigma \mid \text{T} ( \text{w} ) \subset \text{T} ( \text{A} ) \}$ the following theorem (among others) is obtained. Theorem. For all${\text{q}} \in {\text{S}}_\Sigma $, if${\text{A}}$is a saturated chain under$\beta $ then $\Psi ( {\text{qA}} )$is an upper semimodular sublattice of cardinality$|\Psi ( {{\text{qA}}} )|\leqq \frac{1}{{|\Sigma | + 1}} (\begin{smallmatrix} 2|\Sigma | \\ |\Sigma | \end{smallmatrix}) \equiv $The$|\Sigma |$th Catalan number. From the Arrow’s Impossibility Theorem point of view, the results obtained here indicate that majority rule produces transitive results if the collection of voters as a whole can be partitioned into no more than $( |\Sigma |^2 + |\Sigma | )/2$ groups which can be ordered according to the level of disagreement they have with respect to a fixed permutation ${\text{p}}$. On the other hand, by viewing ${\text{S}}_\Sigma $ as a Coxeter group a “novel” combinatorial interpretation of the collection of maximal chains that can be obtained from one another by using only one type of Coxeter transformation is obtained.