Algorithms for Visualization and Exploration of Large Networks

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

• 批准号: RGPIN-2018-05023
• 负责人: Mondal, Debajyoti
• 金额: $ 2.04万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749876
• 关键词: 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 Maps。我们将分析可视化美学之间的权衡，并集中在交互时间的可视化更新。对于每个查询，从头开始计算可视化的技术在需要立即回答许多数据查询时(例如，在金融和商业应用中)失败。我们将设计数据结构来维护部分预计算的可视化，以便可以基于预计算信息快速可视化新的查询或用户交互。我们还将为智能系统开发算法，通过自动建议可视化的重要部分并按需生成可视化摘要来简化网络探索。我们的结果将对加拿大的商业和行业产生积极影响，并使个人能够常规地使用可视化来处理大型网络。我们的算法和软件库将激励交互式网络可视化系统的开发，这将帮助加拿大政府在资源分配、政策制定、安全规划和全球投资方面做出重要决策。在这个项目中接受培训的人将获得开发现实生活中可视化的最受欢迎的技能。因此，它们将在加拿大软件行业未来的发展中发挥关键作用。