Algorithms for Visualization and Exploration of Large Networks

大型网络可视化和探索算法

• 批准号: RGPIN-2018-05023
• 负责人: Mondal, Debajyoti
• 金额: $ 2.04万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=660065
• 关键词: Algorithms; Visualization; Exploration; Large; Networks

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.

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