Algorithms for Visualization and Exploration of Large Networks

我们今天的世界充斥着各种来源的网络，如在线活动、社交媒体、商业交易、交通网络等。因此，网络可视化在加拿大许多部门的决策中变得越来越重要，如商业、安全、行政、应急通信、移民等。可视化过程面临许多挑战。例如，用于检测蜂窝通信网络中的欺诈或新出现的威胁的实时可视化系统将需要复杂的算法来计算数百万个网络节点的布局，创新的可视化技术来揭示动态变化，以及用于交互式过滤和选择的快速数据结构。通过交通网络进行紧急疏散、预测ATM网络中的现金需求、检测官方信息的传播以及揭露社交网络中的谣言，都可能出现类似的场景。虽然有许多潜在的应用，但现有的系统还不足以满足我们的需求。事实上，我们还没有一个明确的算法方法来为大型网络开发一个有效的可视化系统。我们的目标是通过为大型网络可视化开发坚实的算法基础和软件库来解决这些挑战。在短期内，我们将设计用于分层网络可视化的算法，以我们浏览地理地图的方式探索可视化大型网络的概念，例如谷歌或必应地图。我们将分析可视化美学之间的权衡，并专注于交互时间的可视化更新。对于每个查询，从头开始计算可视化的技术，在需要立即回答许多数据查询时就会崩溃，例如在金融和商业应用程序中。我们将设计数据结构来维护部分预计算的可视化，这样新的查询或用户交互可以基于预计算的信息快速可视化。我们还将为智能系统开发算法，通过自动建议可视化的重要部分和生成按需可视化摘要来简化网络探索。我们的研究结果将对加拿大的商业和工业产生积极的影响，并使个人能够经常使用可视化来处理大型网络。我们的算法和软件库将激发交互式网络可视化系统的发展，这将有助于加拿大政府在资源分配、政策制定、安全规划和全球投资方面做出重要决策。在这个项目中接受培训的人将获得开发现实生活可视化的最受欢迎的技能。因此，他们将在加拿大软件产业的未来发展中发挥关键作用。

Our world today is flooded with networks generated from varieties of sources such as online activities, social media, business transactions, transportation networks, etc. Network visualization is thus becoming increasingly important for decision making across many Canadian sectors such as business industries, security, administration, emergency communication, immigration and so on. A visualization process faces many challenges. For example, a real-time visualization system for detecting fraud or emerging threats in a cellular communication network would require sophisticated algorithms to compute a layout of millions of network nodes, innovative visualization techniques to reveal the dynamic changes, and fast data structures for interactive filtering and selection. Similar scenarios may be seen in emergency evacuation through transportation networks, forecasting cash demand in ATM networks, detecting dissemination of official messages and exposing rumours in social networks. Although there are many potential applications, existing systems are not effective enough to meet our need. In fact, we do not yet have a clear algorithmic approach to develop an effective visualization system for large networks. We aim to address these challenges by developing a solid algorithmic foundation and software libraries for large network visualization. In the short term, we will design algorithms for layered network visualization that will explore the concept of visualizing large networks in the way we browse geographic maps, e.g., Google or Bing Maps. We will analyze the trade-offs among the visualization aesthetics, and concentrate on visualization updates in interaction time. Techniques that, for each query, compute the visualization from scratch, fall apart when many data queries need to be answered instantly, e.g., in financial and business applications. We will design data structures to maintain partially precomputed visualizations such that new queries or user interactions can be visualized quickly based on the precomputed information. We will also develop algorithms for intelligent systems that can ease network exploration by automatically suggesting the important parts of the visualization and generating on-demand visualization summaries.Our results will have a positive impact on Canadian business and industries, as well as enable individuals to use visualization routinely to deal with large networks. Our algorithms and software libraries will inspire the development of interactive network visualization systems, which will help Canada's government to make important decisions in resource allocation, policy development, security planning, and global investments. The people trained in this program will gain the most sought-after skills for developing real-life visualization. Thus they will play a key role in the future advancement of Canadian software industries.