Knowledge Discovery by Network Visualization

Hong Zhou, Yingcai Wu, Ming-Yuen Chan, Huamin Qu, Zhengmao Xie, Xiaoming LiEdutainment 2008 · DOI

TL;DR

This paper introduces novel computer graphics techniques to visualize the complex relationships between webpages through hyperlinks. By developing a multi-dimensional encoding scheme and constrained 3D layouts, the authors enable more effective exploration of web linkage data, facilitating knowledge discovery and understanding of hidden patterns.

What Problem Does This Paper Address?

The explosive growth of the internet has led to an overwhelming number of webpages and hyperlinks. While hyperlinks are crucial for understanding webpage importance, clustering, and ranking, manually exploring this vast network is tedious and inefficient. Traditional methods like reading database queries fall short, and existing visualization techniques often struggle with scalability and encoding the rich, multi-dimensional information associated with web links. This paper aims to bridge this gap by providing effective visualization tools to make sense of complex web linkage data.

Methods

The authors propose several novel visualization techniques:

  • 4D Visual Encoding Scheme: This scheme encodes four dimensions of hyperlink data for a single node (webpage, webhost, institution, or domain). Specifically:
  • Size of the node: Represents the size of the webpage, number of webpages in a webhost, etc.
  • Distance from the central node: Encodes the number of outgoing links. Closer nodes indicate more links.
  • Color of the node: Represents the total number of incoming links.
  • Lines/Links: Represent incoming links from outside nodes. The color of these lines encodes the number of outgoing links from the source node to the central node.
  • Pie-style graph: Used to show the percentage of each domain among all domains, clustering nodes by domain.
  • Constrained 3D Layouts: To improve scalability and visibility, they introduce two 3D layouts:
  • Cylindrical View: Nodes are positioned on the surface of a cylinder.
  • Semi-spherical/Dome View: Nodes are positioned on the surface of a semi-sphere. These layouts offer more space for nodes and naturally group nodes at similar distances from the central node, mitigating occlusion issues common in general 3D layouts.

  • Distance Histogram Equalization: For very large datasets where nodes might overlap, this technique redistributes nodes to improve space utilization. It involves:

  • Distance Quantization: Quantizing distances into levels, giving more levels to closer nodes.
  • Distance Histogram Construction: Counting nodes within each distance level.
  • Distance Histogram Equalization: Applying histogram equalization to redistribute nodes more evenly.
  • 3D Treemap for Linkage Data: Extending traditional treemaps, this method visualizes hierarchical structures along with linkage information. The hierarchical structure of boxes encodes the webpage hierarchy. Users can then use the size and color of boxes to encode two additional node attributes (e.g., node size, number of self-links, outgoing links, or incoming links). The 3D aspect allows for encoding another attribute as the height of the box.

Datasets

The primary dataset used for evaluation consists of webpages from the ".edu.cn" domain, collected from Peking University. This dataset includes approximately 820 Chinese educational institutions and 4,333 webhosts. The paper does not introduce new benchmarks but uses this real-world dataset to demonstrate the effectiveness of their visualization techniques.

Key Insights and Ideas

  • Visualizing Multi-dimensional Data: The core insight is that by cleverly encoding multiple attributes (size, distance, color, line properties) into visual elements, complex relationships within web linkage data can be made comprehensible.
  • Scalability through 3D and Layout Techniques: The paper highlights that traditional 2D node-link diagrams struggle with large datasets. Constrained 3D layouts and histogram equalization are crucial for managing visual clutter and improving the exploration of dense networks.
  • Bridging Hierarchical and Linkage Data: The extension of treemaps to incorporate linkage information is a significant contribution, allowing users to simultaneously understand both the structural hierarchy and the interconnections between entities.
  • Subjectivity in Web Data Exploration: The user study revealed that tasks involving subjective queries (e.g., "relatively weak connection") are difficult to formulate in traditional SQL but are well-suited for visual exploration, where users can make judgments based on the overall visual context.
  • Unexpected Discoveries: Users, even with limited training, were able to discover interesting patterns and previously unknown web entities, demonstrating the system's potential for knowledge discovery.

Key Results

  • User Study Effectiveness: A user study with ten participants demonstrated the usability and effectiveness of the proposed techniques.
  • Task 1 (4D Encoding): Average response time was 12.3 seconds. Users found the system good for subjective tasks where formulating precise SQL queries is difficult.
  • Task 2 (Distance Histogram Equalization): Group A (without equalization) took twice as long as Group B (with equalization). The equalization significantly improved space usage and led to more reasonable and accurate answers.
  • Task 3 (2D vs. 3D Layouts): Group B (3D layouts) took three times longer than Group A (2D layouts) due to rotation and exploration time. However, Group B users tended to choose fewer, more focused webhosts, while Group A users sometimes picked multiple choices.
  • Qualitative Findings: Participants found the system fascinating and were able to discover interesting information, such as the prominence of certain educational portals and BBS webhosts. They were also surprised by some linkage patterns, like large, "hot" nodes being far from the central node.

Limitations and Future Work

  • Current Focus on Medium-Sized Data: The authors acknowledge that their current work primarily focuses on effective visualization for medium-sized datasets.
  • Future Work:
    • Large Data Visualization: Developing techniques to visualize even larger datasets.
  • More Dimensions: Encoding more than five dimensions of data.
  • Clickstream and History Data: Incorporating clickstream data and webpage history for richer exploration.
  • General Network Visualization: Extending the methods to a broader range of general network visualization problems beyond webpages.

Summary updated

BibTeX
@inproceedings{zhou2008knowledge,
  author = {Hong Zhou and Yingcai Wu and Ming-Yuen Chan and Huamin Qu and Zhengmao Xie and Xiaoming Li},
  title = {{Knowledge Discovery by Network Visualization}},
  booktitle = {Edutainment},
  year = {2008},
  doi = {10.1007/978-3-540-69736-7\_26},
}
Figure