Pathfinder: Visual Analysis of Paths in Graphs

The analysis of paths in graphs is highly relevant in many domains. Typically, path‐related tasks are performed in node‐link layouts. Unfortunately, graph layouts often do not scale to the size of many real world networks. Also, many networks are multivariate, i.e., contain rich attribute sets associated with the nodes and edges. These attributes are often critical in judging paths, but directly visualizing attributes in a graph layout exacerbates the scalability problem. In this paper, we present visual analysis solutions dedicated to path‐related tasks in large and highly multivariate graphs. We show that by focusing on paths, we can address the scalability problem of multivariate graph visualization, equipping analysts with a powerful tool to explore large graphs. We introduce Pathfinder, a technique that provides visual methods to query paths, while considering various constraints. The resulting set of paths is visualized in both a ranked list and as a node‐link diagram. For the paths in the list, we display rich attribute data associated with nodes and edges, and the node‐link diagram provides topological context. The paths can be ranked based on topological properties, such as path length or average node degree, and scores derived from attribute data. Pathfinder is designed to scale to graphs with tens of thousands of nodes and edges by employing strategies such as incremental query results. We demonstrate Pathfinder's fitness for use in scenarios with data from a coauthor network and biological pathways.     

TMNVis: Visual analysis of evolution in temporal multivariate network at multiple granularities

Temporal (Dynamic) multivariate networks consist of objects and relationships with a variety of attributes, and the networks change over time. Exploring such kind of networks in visualization is of great significance and full of challenges as its time-varying and multivariate nature. Most of the existing dynamic network visualization techniques focus on the topological structure evolution lacking of exploration on the multivariate data (multiple attributes) thoroughly, and do not cover comprehensive analyses on multiple granularities. In this paper, we propose TMNVis, an interactive visualization system to explore the evolution of temporal multivariate network. Firstly we list a series of tasks on three granularities: global level, subgroup level and individual level. Secondly three main views, which rely mainly on timeline-based method while animation subsidiary, are designed to resolve the analysis tasks. Thirdly we design a series of flexible interactions and develop a prototype system. At last we verify the effectiveness and usefulness of TMNVis using a real-world academic collaboration data.     

语义增强的大规模多元图简化可视分析方法

网络图可视化可以有效展示网络节点之间的连接关系,广泛应用于诸多领域,如社交网络、知识图谱、生物基因网络等.随着网络数据规模的不断增加,如何简化表达大规模网络图结构已成为图可视化领域中的研究热点.经典的网络图简化可视化方法主要包括图采样、边绑定和图聚类等技术,在减少大量点线交叉造成的视觉紊乱的基础上,提高用户对大规模网络结构的探索和认知效率.然而,上述方法主要侧重于网络图中的拓扑结构,却较少考虑和利用多元图节点的多维属性特征,难以有效提取和表达语义信息,从而无法帮助用户理解大规模多元网络的拓扑结构与多维属性之间的内在关联,为大规模多元图的认知和理解带来困难.因此,本文提出一种语义增强的大规模多元图简化可视分析方法,首先在基于模块度的图聚类算法基础上提取出网络图的层次结构;其次通过多维属性信息熵的计算和比较分析,对网络层次结构进行自适应划分,筛选出具有最优属性聚集特征的社团;进而设计交互便捷的多个关联视图来展示社团之间的拓扑结构、层次关系和属性分布,从不同角度帮助用户分析多维属性在社团形成和网络演化中的作用.大量实验结果表明,本文方法能够有效简化大规模多元图的视觉表达,可以快速分析不同应用领域大规模多元图的关联结构与语义构成,具有较强的实用性.     

The State of the Art in Visualizing Dynamic Multivariate Networks

Most real-world networks are both dynamic and multivariate in nature, meaning that the network is associated with various attributes and both the network structure and attributes evolve over time. Visualizing dynamic multivariate networks is of great significance to the visualization community because of their wide applications across multiple domains. However, it remains challenging because the techniques should focus on representing the network structure, attributes and their evolution concurrently. Many real-world network analysis tasks require the concurrent usage of the three aspects of the dynamic multivariate networks. In this paper, we analyze current techniques and present a taxonomy to classify the existing visualization techniques based on three aspects: temporal encoding, topology encoding, and attribute encoding. Finally, we survey application areas and evaluation methods; and discuss challenges for future research.     

Unfolding Edges: Adding Context to Edges in Multivariate Graph Visualization

Existing work on visualizing multivariate graphs is primarily concerned with representing the attributes of nodes. Even though edges are the constitutive elements of networks, there have been only few attempts to visualize attributes of edges. In this work, we focus on the critical importance of edge attributes for interpreting network visualizations and building trust in the underlying data. We propose ‘unfolding of edges’ as an interactive approach to integrate multivariate edge attributes dynamically into existing node-link diagrams. Unfolding edges is an in-situ approach that gradually transforms basic links into detailed representations of the associated edge attributes. This approach extends focus+context, semantic zoom, and animated transitions for network visualizations to accommodate edge details on-demand without cluttering the overall graph layout. We explore the design space for the unfolding of edges, which covers aspects of making space for the unfolding, of actually representing the edge context, and of navigating between edges. To demonstrate the utility of our approach, we present two case studies in the context of historical network analysis and computational social science. For these, web-based prototypes were implemented based on which we conducted interviews with domain experts. The experts' feedback suggests that the proposed unfolding of edges is a useful tool for exploring rich edge information of multivariate graphs.     

AHNG: Representation learning on attributed heterogeneous network

Network embedding aims to encode nodes into a low-dimensional space with the structure and inherent properties of the networks preserved. It is an upstream technique for network analyses such as link prediction and node clustering. Most existing efforts are devoted to homogeneous or heterogeneous plain networks. However, networks in real-world scenarios are usually heterogeneous and not plain, i.e., they contain multi-type nodes/links and diverse node attributes. We refer such kind of networks with both heterogeneities and attributes as attributed heterogeneous networks (AHNs). Embedding AHNs faces two challenges: (1) how to fuse heterogeneous information sources including network structures, semantic information and node attributes; (2) how to capture uncertainty of node embeddings caused by diverse attributes. To tackle these challenges, we propose a unified embedding model which represents each node in an AHN with a Gaussian distribution (AHNG). AHNG fuses multi-type nodes/links and diverse attributes through a two-layer neural network and captures the uncertainty by embedding nodes as Gaussian distributions. Furthermore, the incorporation of node attributes makes AHNG inductive, embedding previously unseen nodes or isolated nodes without additional training. Extensive experiments on a large real-world dataset validate the effectiveness and efficiency of the proposed model.     

GlyphLink: An interactive visualization approach for semantic graphs

Graph analysis by data visualization involves achieving a series of topology-based tasks. When the graph data belongs to a data domain that contains multiple node and link types, as in the case of semantic graphs, topology-based tasks become more challenging. To reduce visual complexity in semantic graphs, we propose an approach which is based on applying relational operations such as selecting and joining nodes of different types. We use node aggregation to reflect the relational operations to the graph. We introduce glyphs for representing aggregated nodes. Using glyphs lets us encode connectivity information of multiple nodes with a single glyph. We also use visual parameters of the glyph to encode node attributes or type specific information. Rather than doing the operations in the data abstraction layer and presenting the user with the resulting visualization, we propose an interactive approach where the user can iteratively apply the relational operations directly on the visualization. We present the efficiency of our method by the results of a usability study that includes a case study on a subset of the International Movie Database. The results of the controlled experiment in our usability study indicate a statistically significant contribution in reducing the completion time of the evaluation tasks.     

A self-processing network model for relational databases

In this paper, a model which combines relational databases with self-processing networks is proposed in order to improve the performance of very large databases. The proposed model uses an approach which is radically different from all other distributed database models, where each computer processes a portion of the database. In the self-processing network model, the network structure which consists of nodes and connections, captures the data and the relationships by assigning them unique, connected control, and data nodes. The network activity is the mechanism that performs the relational algebra operations. No data transmission is needed, and since data nodes are common to all the relations, integrity and elimination of data redundancy are achieved. An extension of the model, by interconnecting the data nodes via weighted links, provides us with properties that are embedded in neural networks, such as fuzziness and learning.     

GraphDice: A System for Exploring Multivariate Social Networks

Social networks collected by historians or sociologists typically have a large number of actors and edge attributes. Applying social network analysis (SNA) algorithms to these networks produces additional attributes such as degree, centrality, and clustering coefficients. Understanding the effects of this plethora of attributes is one of the main challenges of multivariate SNA. We present the design of GraphDice, a multivariate network visualization system for exploring the attribute space of edges and actors. GraphDice builds upon the ScatterDice system for its main multidimensional navigation paradigm, and extends it with novel mechanisms to support network exploration in general and SNA tasks in particular. Novel mechanisms include visualization of attributes of interval type and projection of numerical edge attributes to node attributes. We show how these extensions to the original ScatterDice system allow to support complex visual analysis tasks on networks with hundreds of actors and up to 30 attributes, while providing a simple and consistent interface for interacting with network data.     

基于节点交互度的社会网络链路预测

链路预测是通过已知的网络拓扑和节点属性挖掘未来时刻节点潜在关系的重要手段, 是预测缺失链路和识别虚假链路的有效方法, 在研究社会网络结构演化中具有现实意义. 传统的链路预测方法基于节点信息或路径信息相似性进行预测, 然而, 前者考虑指标单一导致预测精度受限, 后者由于计算复杂度过高不适合在规模较大网络中应用. 通过对网络拓扑结构的分析, 本文提出一种基于节点交互度(interacting degree of nodes, IDN)的社会网络链路预测方法. 该方法首先根据网络中节点间的路径特征, 引入了节点效率的概念, 从而提高对于没有公共邻居节点之间链路预测的准确性; 为了进一步挖掘节点间共同邻居的相关属性, 借助分析节点间共同邻居的拓扑结构, 该方法还创新性地整合了路径特征和局部信息, 提出了社会网络节点交互度的定义, 准确刻画出节点间的相似度, 从而增强网络链路的预测能力; 最后, 本文借助6个真实网络数据集对IDN方法进行验证, 实验结果表明, 相比于目前的主流算法, 本文提出的方法在AUC和Precision两个评价指标上均表现出更优的预测性能, 预测结果平均分别提升22%和54%. 因此节点交互度的提出在链路预测方面具有很高的可行性和有效性.     

Understanding Indirect Causal Relationships in Node‐Link Graphs

To find correlations and cause and effect relationships in multivariate data sets is central in many data analysis problems. A common way of representing causal relations among variables is to use node‐link diagrams, where nodes depict variables and edges show relationships between them. When performing a causal analysis, analysts may be biased by the position of collected evidences, especially when they are at the top of a list. This is of crucial importance since finding a root cause or a derived effect, and searching for causal chains of inferences are essential analytic tasks when investigating causal relationships. In this paper, we examine whether sequential ordering influences understanding of indirect causal relationships and whether it improves readability of multi‐attribute causal diagrams. Moreover, we see how people reason to identify a root cause or a derived effect. The results of our design study show that sequential ordering does not play a crucial role when analyzing causal relationships, but many connections from/to a variable and higher strength/certainty values may influence the process of finding a root cause and a derived effect.     

Design space exploration of reliable networked embedded systems

In this paper, a new methodology is presented for topology optimization of networked embedded systems as they occur in automotive and avionic systems as well as wireless sensor networks. By introducing a model which is (1) suitable for heterogeneous networks with different communication bandwidths, (2) modeling of routing restrictions, and (3) flexible binding of tasks onto processors, current design issues of networked embedded systems can be investigated. On the basis of this model, the presented methodology firstly allocates the required resources which can be communication links as well as computational nodes and secondly binds the functionality onto the nodes and the data dependencies onto the links such that no routing restrictions will be violated or capacities on communication links will be exceeded. Due to the often error-prone communication in networks, we allow for routing each data dependency over multiple routes in the networks. With this strategy, our methodology is able to increase the reliability of the entire system. This reliability analysis is based on Binary Decision Diagrams (BDDs) and is integrated in our multi-objective design space exploration. By applying Evolutionary Algorithms, we are able to consider multiple objectives simultaneously during the optimization process and allow for a subsequent unbiased decision making. An experimental evaluation as well as a demonstration of a case study from the field of automotive electronics will show the applicability of the presented approach.     

Efficient resource discovery in self‐organized unstructured peer‐to‐peer networks

In unstructured peer‐to‐peer (P2P) networks, two autonomous peer nodes can be connected if users in those nodes are interested in each other's data. Owing to the similarity between P2P networks and social networks, where peer nodes can be regarded as people and connections can be regarded as relationships, social strategies are useful for improving the performance of resource discovery by self‐organizing autonomous peers on unstructured P2P networks. In this paper, we present an efficient social‐like peer‐to‐peer (ESLP) method for resource discovery by mimicking different human behaviours in social networks. ESLP has been simulated in a dynamic environment with a growing number of peer nodes. From the simulation results and analysis, ESLP achieved better performance than current methods. Copyright © 2008 John Wiley & Sons, Ltd.     

Sign prediction in sparse social networks using clustering and collaborative filtering

Today, social networks have created a wide variety of relationships between users. Friendships on Facebook and trust in the Epinions network are examples of these relationships. Most social media research has often focused on positive interpersonal relationships, such as friendships. However, in many real-world applications, there are also networks of negative relationships whose communication between users is either distrustful or hostile in nature. Such networks are called signed networks. In this work, sign prediction is made based on existing links between nodes. However, in real signed networks, links between nodes are usually sparse and sometimes absent. Therefore, existing methods are not appropriate to address the challenges of accurate sign prediction. To address the sparsity problem, this work aims to propose a method to predict the sign of positive and negative links based on clustering and collaborative filtering methods. Network clustering is done in such a way that the number of negative links between the clusters and the number of positive links within the clusters are as large as possible. As a result, the clusters are as close as possible to social balance. The main contribution of this work is using clustering and collaborative filtering methods, as well as proposing a new similarity criterion, to overcome the data sparseness problem and predict the unknown sign of links. Evaluations on the Epinions network have shown that the prediction accuracy of the proposed method has improved by 8% compared to previous studies.

     

A block-based generative model for attributed network embedding

Attributed network embedding has attracted plenty of interest in recent years. It aims to learn task-independent, low-dimensional, and continuous vectors for nodes preserving both topology and attribute information. Most of the existing methods, such as random-walk based methods and GCNs, mainly focus on the local information, i.e., the attributes of the neighbours. Thus, they have been well studied for assortative networks (i.e., networks with communities) but ignored disassortative networks (i.e., networks with multipartite, hubs, and hybrid structures), which are common in the real world. To model both assortative and disassortative networks, we propose a block-based generative model for attributed network embedding from a probability perspective. Specifically, the nodes are assigned to several blocks wherein the nodes in the same block share the similar linkage patterns. These patterns can define assortative networks containing communities or disassortative networks with the multipartite, hub, or any hybrid structures. To preserve the attribute information, we assume that each node has a hidden embedding related to its assigned block. We use a neural network to characterize the nonlinearity between node embeddings and node attributes. We perform extensive experiments on real-world and synthetic attributed networks. The results show that our proposed method consistently outperforms state-of-the-art embedding methods for both clustering and classification tasks, especially on disassortative networks.

     

A neural network-based approach for user experience assessment

The objective of this study is to approximate the links between user satisfaction and its determinants without having the restrictions of common statistical procedures such as linearity, symmetry and normality. For this reason, artificial neural networks are utilised and trained with the observations of an extensive survey on user satisfaction with respect to website attributes. Each observation includes evaluations about the performance of 18 specific and 9 general website attributes as well as an evaluation about overall user satisfaction. The analysis results indicate that website attributes present different impacts on satisfaction whereas the relationships found feature both asymmetry and nonlinearity. Finally, function approximation using neural networks is found to be appropriate for estimating such kind of relationships providing valuable information about satisfaction's formation.     

Multi-relational reinforcement for computing credibility of nodes

Nowadays, growing number of social networks are available on the internet, with which users can conveniently make friends, share information, and exchange ideas with each other. As the result, large amount of data are generated from activities of those users. Such data are regarded as valuable resources to support different mining tasks, such as predicting friends for a user, ranking users in terms of their influence on the social network, or identifying communities with common interests. Traditional algorithms for those tasks are often designed under the assumption that a user selects another user as his friend based on their common interests. As a matter of fact, users on a social network may not always develop their friends with common interest. For example, a user may randomly select other users as his friends just in order to attract more links reversely from them. Therefore, such links may not indicate his influence. In this paper, we study the user rank problem in terms of their ‘real’ influences. For this sake, common interest relationships among users are established besides their friend relationships. Then, the credible trust link from one node to another is on account of their similarities, which means the more similar the two users, the more credible their trust relation. So the credibility of a node is high if its trust inlinks are credible enough. In this work, we propose a framework that computes the credibility of nodes on a multi-relational network using reinforcement techniques. To the best of our knowledge, this is the first work to assess credibility exploited knowledge on multi-relational social networks. The experimental results on real data sets show that our framework is effective.     

基于空间映射的顶点带属性网络的链接预测

提出了基于空间映射的顶点带属性网络的链接预测算法。顶点带属性网络包含拓扑及顶点属性两种信息,为了综合考虑这两种信息,将二者同时映射到另一空间。完成空间映射后,在新的空间计算顶点的相似度,并以此来预测链接存在的可能性。提出分步交叉迭代的方法来取得最优的映射矩阵,以在新的空间中有效融合拓扑信息与顶点属性信息。实验结果证明了空间映射方法的正确性,所提出的基于空间映射的方法能够取得较高质量的预测结果。     

Text-enhanced network representation learning

Network representation learning called NRL for short aims at embedding various networks into lowdimensional continuous distributed vector spaces. Most existing representation learning methods focus on learning representations purely based on the network topology, i.e., the linkage relationships between network nodes, but the nodes in lots of networks may contain rich text features, which are beneficial to network analysis tasks, such as node classification, link prediction and so on. In this paper, we propose a novel network representation learning model, which is named as Text-Enhanced Network Representation Learning called TENR for short, by introducing text features of the nodes to learn more discriminative network representations, which come from joint learning of both the network topology and text features, and include common influencing factors of both parties. In the experiments, we evaluate our proposed method and other baseline methods on the task of node classification. The experimental results demonstrate that our method outperforms other baseline methods on three real-world datasets.     

基于属性和关系的OLAP算法研究

随着社会网络的兴起,尤其是OLAP概念的提出,人们提出了很多对OLAP研究的算法,其中对图聚类算法的研究也引起了人们的广泛关注。但是这类算法大多数只是关注节点的属性或者节点之间的关系,而很少同时考虑到节点的属性和它们之间的关系。文中从这两个方面考虑的同时,在划分节点的时候更考虑到了要划分的节点在整个组中的紧密性,把网络中的模块化运用到节点的划分中,使得划分的结果更具有现实意义,而且很好地把Q函数的理论应用到社区的划分过程中,更加注重了单个节点对整个社区划分的影响,使得划分之后的各个子社区内部关系更加紧密。