Finding overlapping communities in a complex network of social linkages and Internet of things

Online social networks play an important role in today’s Internet. These social networks contain huge amounts of data and the integrated framework of SN with Internet of things (IoT) presents a challenging problem. IoT is the ubiquitous interconnection of everyday items of interest (things), providing connectivity anytime, anywhere, and with anything. Like biological, co-authorship, and virus-spread networks, IoT and Social Network (SN) can be characterized to be complex networks containing substantial useful information. In the past few years, community detection in graphs has been an active area of research (Lee and Won in Proceedings of IEEE SoutheastCon, pp. 1–5, 2012). Many graph mining algorithms have been proposed, but none of them can help in capturing an important dimension of SNs, which is friendship. A friend circle expands with the help of mutual friends, and, thus, mutual friends play an important role in social networks’ growth. We propose two graph clustering algorithms: one for undirected graphs such as Facebook and Google+, and the other for directed graphs such as Twitter. The algorithms extract communities, and based on the access control policy nodes share resources (things). In the proposed Community Detection in Integrated IoT and SN (CDIISN) algorithm, we divide the nodes/actors of complex networks into basic, and IoT nodes. We, then, execute the community detection algorithm on them. We take nodes of a graph as members of a SN, and edges depicting the relations between the nodes. The CDIISN algorithm is purely deterministic, and no fuzzy communities are formed. It is known that one community detection algorithm is not suitable for all types of networks. For different network structures, different algorithms exhibit different results, and methods of execution. However, in our proposed method, the community detection algorithm can be modified as desired by a user based on the network connections. The proposed community detection approach is unique in the sense that a user can define his community detection criteria based on the kind of network.     

用多层次聚类法完成的大规模关系图的可视化

提出了一种新的大规模图形可视化技术.它可显示含有几万个接点和边的大规模关系图.为了完成对图形的抽象化。一个多层次的聚类图形从原始的大规模关系图中抽取了出来.这种抽取是建立在大规模关系图的内在结构基础上来完成的.一种递规封入式的几何划分算法被应用来完成对几何空间的优化,在具体的制图技术上,使用了一种用力导向布局算法和环形制图法相结合的新方法,从而完成了对显示空间的优化和美擘上的优化.同时也讨论了相关的人机交互技术,所采用的人机交互算法不仅能让使用者从上到下层次式地浏览整个聚类图形。同时也能提供多层次聚类图形的并行浏览.动画技术也同时被运用,以保护使用者的精神图不被打乱.     

Edge-colouring of join graphs

A join graph is the complete union of two arbitrary graphs. We give sufficient conditions for a join graph to be 1-factorizable. As a consequence of our results, the Hilton’s Overfull Subgraph Conjecture holds true for several subclasses of join graphs.     

Action graphs and user performance analysis

A user operating an interactive system performs actions such as “pressing a button” and these actions cause state transitions in the system. However to perform an action, a user has to do what amounts to a state transition themselves, from the state of having completed the previous action to the state of starting to perform the next action; this user transition is out of step with the system's transition. This paper introduces action graphs, an elegant way of making user transitions explicit in the arcs of a graph derived from the system specification. Essentially, a conventional transition system has arcs labeled in the form “user performs action A” whereas an action graph has arcs labelled in the form “having performed action P, the user performs Q.” Action graphs support many modelling techniques (such as GOMS, KLM or shortest paths) that could have been applied to the user's actions or to the system graph, but because it combines both, the modelling techniques can be used more powerfully.Action graphs can be used to directly apply user performance metrics and hence perform formal evaluations of interactive systems. The Fitts Law is one of the simplest and most robust of such user modelling techniques, and is used as an illustration of the value of action graphs in this paper. Action graphs can help analyze particular tasks, any sample of tasks, or all possible tasks a device supports—which would be impractical for empirical evaluations. This is an important result for analyzing safety critical interactive systems, where it is important to cover all possible tasks in testing even when doing so is not feasible using human participants because of the complexity of the system.An algorithm is presented for the construction of action graphs. Action graphs are then used to study devices (a consumer device, a digital multimeter, an infusion pump) and results suggest that: optimal time is correlated with keystroke count, and that keyboard layout has little impact on optimal times. Many other applications of action graphs are suggested.     

Evaluating esthetics for user-sketched layouts of clustered graphs with known clustering information

This paper aims to empirically analyze the esthetics for user-sketched layouts of clustered graphs with known clustering information. In our experiments, given not only the adjacency list of a clustered graph but also its predefined clustering information, each participant was asked to manually sketch clustered graphs “nicely” from scratch on a tablet system using a stylus. Different from previous works, the main concern in this paper is on which graph drawing esthetics people favor when sketching their own drawings of clustered graphs with known clustering information. Another concern of this paper is on the esthetics of clustered graph layouts employed by participants which include not only characteristics and structures of the final graph layouts but also the behavior of user's sketching process (including layout creation and adjustment). By observing all layouts and drawing processes, the drawing strategies which participants applied and the drawing esthetics are analyzed. Results show that most participants were unsurprisingly able to draw graphs with clear presence of bridge edges and clustering cohesiveness; more importantly, to distinguish clusters within the restricted-size tablet screen during the drawing process, some of the participants were still able to make each cluster with fewer edge crossings, more symmetries, and more alignment of grid in a smaller drawing area where the cluster spreads. Our results support that to alleviate user's complex drawing tasks, aside from the grid-based editing function suggested by the previous work, graph drawing systems should also provide the clustering information if the structure of the graph to be drawn is known.     

A regularized graph layout framework for dynamic network visualization

Many real-world networks, including social and information networks, are dynamic structures that evolve over time. Such dynamic networks are typically visualized using a sequence of static graph layouts. In addition to providing a visual representation of the network structure at each time step, the sequence should preserve the mental map between layouts of consecutive time steps to allow a human to interpret the temporal evolution of the network. In this paper, we propose a framework for dynamic network visualization in the on-line setting where only present and past graph snapshots are available to create the present layout. The proposed framework creates regularized graph layouts by augmenting the cost function of a static graph layout algorithm with a grouping penalty, which discourages nodes from deviating too far from other nodes belonging to the same group, and a temporal penalty, which discourages large node movements between consecutive time steps. The penalties increase the stability of the layout sequence, thus preserving the mental map. We introduce two dynamic layout algorithms within the proposed framework, namely dynamic multidimensional scaling and dynamic graph Laplacian layout. We apply these algorithms on several data sets to illustrate the importance of both grouping and temporal regularization for producing interpretable visualizations of dynamic networks.     

Inverse Markov Process Based Constrained Dynamic Graph Layout

In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout.Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints.To solve this problem,we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change,according to which different constraints can be set.These constraints,along with stress function,generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs.Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Larger crossing angles make graphs easier to read

Objective: Aesthetics are important in algorithm design and graph evaluation. This paper presents two user studies that were conducted to investigate the impact of crossing angles on human graph comprehension.Method and results: These two studies together demonstrate our newly proposed two-step approach for testing graph aesthetics. The first study is a controlled experiment with purposely-generated graphs. Twenty-two subjects participated in the study and were asked to determine the length of a path which was crossed by a set of parallel edges at different angles. The result of an analysis of variance showed that larger crossing angles induced better task performance. The second study was a non-controlled experiment with general real world graphs. Thirty-seven subjects participated in the study and were asked to find the shortest path of two pre-selected nodes in a set of graph drawings. The results of simple regression tests confirmed the negative effect of small crossing angles. This study also showed that among our four proposed candidates, the minimum crossing angle on the path was the best measure for the aesthetic when path finding is important.Conclusion: Larger crossing angles make graphs easier to read.Implications: In situations where crossings cannot be completely removed (for example, graphs are non-planar, or a drawing convention is applied), or where effort needed to remove all crossings cannot be justified, the crossing angle should be maximized to reduce the negative impact of crossings to the minimum.     

Drawing graphs with nonuniform nodes using potential fields

Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution.     

Augmenting Node-Link Diagrams with Topographic Attribute Maps

We propose a novel visualization technique for graphs that are attributed with scalar data. In many scenarios, these attributes (e.g., birth date in a family network) provide ambient context information for the graph structure, whose consideration is important for different visual graph analysis tasks. Graph attributes are usually conveyed using different visual representations (e.g., color, size, shape) or by reordering the graph structure according to the attribute domain (e.g., timelines). While visual encodings allow graphs to be arranged in a readable layout, assessing contextual information such as the relative similarities of attributes across the graph is often cumbersome. In contrast, attribute-based graph reordering serves the comparison task of attributes, but typically strongly impairs the readability of the structural information given by the graph's topology. In this work, we augment force-directed node-link diagrams with a continuous ambient representation of the attribute context. This way, we provide a consistent overview of the graph's topological structure as well as its attributes, supporting a wide range of graph-related analysis tasks. We resort to an intuitive height field metaphor, illustrated by a topographic map rendering using contour lines and suitable color maps. Contour lines visually connect nodes of similar attribute values, and depict their relative arrangement within the global context. Moreover, our contextual representation supports visualizing attribute value ranges associated with graph nodes (e.g., lifespans in a family network) as trajectories routed through this height field. We discuss how user interaction with both the structural and the contextual information fosters exploratory graph analysis tasks. The effectiveness and versatility of our technique is confirmed in a user study and case studies from various application domains.     

Colored Simultaneous Geometric Embeddings and?Universal Pointsets

Universal pointsets can be used for visualizing multiple relationships on the same set of objects or for visualizing dynamic graph processes. In simultaneous geometric embeddings, the same point in the plane is used to represent the same object as a way to preserve the viewer??s mental map. In colored simultaneous embeddings this restriction is relaxed, by allowing a given object to map to a subset of points in the plane. Specifically, consider a set of graphs on the same set of n vertices partitioned into k colors. Finding a corresponding set of k-colored points in the plane such that each vertex is mapped to a point of the same color so as to allow a straight-line plane drawing of each graph is the problem of colored simultaneous geometric embedding. For n-vertex paths, we show that there exist universal pointsets of size n, colored with two or three colors. We use this result to construct colored simultaneous geometric embeddings for a 2-colored tree together with any number of 2-colored paths, and more generally, a?2-colored outerplanar graph together with any number of 2-colored paths. For n-vertex trees, we construct small near-universal pointsets for 3-colored caterpillars of size n, 3-colored radius-2 stars of size n+3, and 2-colored spiders of size n. For n-vertex outerplanar graphs, we show that these same universal pointsets also suffice for 3-colored K ₃-caterpillars, 3-colored K ₃-stars, and 2-colored fans, respectively. We also present several negative results, showing that there exist a 2-colored planar graph and pseudo-forest, three 3-colored outerplanar graphs, four 4-colored pseudo-forests, three 5-colored pseudo-forests, five 5-colored paths, two 6-colored biconnected outerplanar graphs, three 6-colored cycles, four 6-colored paths, and three 9-colored paths that cannot be simultaneously embedded.     

A Visualization Framework and User Studies for Overloaded Orthogonal Drawings

Overloaded orthogonal drawing (OOD) is a recent graph visualization style specifically conceived for directed graphs. It merges the advantages of some popular drawing conventions like layered drawings and orthogonal drawings, and provides additional support for some common analysis tasks. We present a visualization framework called DAGView, which implements algorithms and graphical features for the OOD style. Besides the algorithm for acyclic digraphs, the DAGView framework implements extensions to visualize both digraphs with cycles and undirected graphs, with the additional possibility of taking into account user preferences and constraints. It also supports an interactive visualization of clustered digraphs, based on the use of strongly connected components. Moreover, we describe an experimental user study, aimed to investigate the usability of OOD within the DAGView framework. The results of our study suggest that OOD can be effectively exploited to perform some basic tasks of analysis in a faster and more accurate way when compared to other drawing styles for directed graphs.     

A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners

A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings.     

Techniques for Edge Stratification of Complex Graph Drawings

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.     

Kronecker product graph matching

In this paper the Interpolator-based Kronecker product graph matching (IBKPGM) algorithm for performing attributed graph matching is presented. The IBKPGM algorithm is based on the Kronecker product graph matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of graph matching problems based on attributed graphs, allowing the structure of the graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input graphs as well as between all edges of the reference and input graphs are avoided.     

Supporting sketch-based retrieval from a library of reusable behaviours

Building the behaviour for non-player characters in a game is a complex collaborative task among AI designers and programmers. In this paper we present a visual authoring tool for game designers that supports behaviour reuse. We describe a visual editor, capable of storing, indexing, retrieving and reusing behaviours previously designed by AI programmers. One of the most notable features of our editor is its capability for sketch-based retrieval: searching in a repository for behaviours that are similar to the one the user is drawing, and making suggestions about how to complete it. As this process relies on graph behaviour comparison, in this paper, we describe different algorithms for graph comparison, and demonstrate, through empirical evaluation in a particular test domain, that we can provide structure-based similarity for graphs that preserves behaviour similarity and can be computed at reasonable cost.     

An Algorithm for Straight-Line Drawing of Planar Graphs

We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing graphs ``nicely,' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely. Received September 21, 1995; revised March 15, 1996.     

Retrieving keyworded subgraphs with graph ranking score

Keyword queries have long been popular to search engines and to the information retrieval community and have recently gained momentum for its usage in the expert systems community. The conventional semantics for processing a user query is to find a set of top-k web pages such that each page contains all user keywords. Recently, this semantics has been extended to find a set of cohesively interconnected pages, each of which contains one of the query keywords scattered across these pages. The keyword query having the extended semantics (i.e., more than a list of keywords hyperlinked with each other) is referred to the graph query. In case of the graph query, all the query keywords may not be present on a single Web page. Thus, a set of Web pages with the corresponding hyperlinks need to be presented as the search result. The existing search systems reveal serious performance problem due to their failure to integrate information from multiple connected resources so that an efficient algorithm for keyword query over graph-structured data is proposed. It integrates information from multiple connected nodes of the graph and generates result trees with the occurrence of all the query keywords. We also investigate a ranking measure called graph ranking score (GRS) to evaluate the relevant graph results so that the score can generate a scalar value for keywords as well as for the topology.     

Locating communities on graphs with variations in community sizes

A fundamental problem in networking and computing is community detection. Various applications like finding web communities, uncovering the structure of social networks, or even analyzing a graph’s structure to uncover Internet attacks are just some of the applications for which community detection is important. In this paper, we propose an algorithm that finds the entire community structure of a network, represented by an undirected, unweighted graph, based on local interactions between neighboring nodes and on an unsupervised centralized clustering algorithm. The novelty of the proposed approach is the fact that the algorithm is based on the use of network coordinates computed by a distributed algorithm. Experimental results and comparisons with the Lancichinetti et al. method (Phys. Rev. E 80(5 Pt 2), 056117, 2009; New J. Phys. 11(3), 033015, 2009) are presented for a variety of benchmark graphs with known community structure, derived by varying a number of graph parameters. Emphasis is given on benchmark graphs with significant variations in the size of their communities. Further experimental results are presented for two real dataset graphs, namely the Enron, and the Epinions graphs, from SNAP, the Stanford Large Network Dataset Collection. The experimental results demonstrate the high performance of our algorithm in terms of accuracy to detect communities, and its computational efficiency.