Algorithms for Visualization and Exploration of Large Networks

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

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.