Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$48,000.00

Community-Centric Mining of Large-Scale Dynamic Graphs

FY 2023-24

Summary
Graphs are ubiquitous and the most natural representation for many real world data coming from web, social, and knowledge networks, communication networks, transaction networks, and epidemiological networks. They are growing at an unprecedented rate. For instance, the web graph consists of more than a trillion websites, and the social graphs of Facebook, Twitter, and Weibo, have billions of users with many friend/follow connections per user. Consequently, storing such graphs and answering queries, mining patterns, and producing insights are becoming very challenging. These graphs also come with complex and diverse types on their nodes and edges which can represent people, items, and their interactions making for truly heterogeneous information networks. Furthermore, the information can be imprecise and uncertain, thus necessitating a probabilistic reasoning on the data. Not only is there a pressing need for new algorithms to handle these complex graph datasets, but scalability has to be addressed from the ground up to serve the real needs of organizations for industrial strength graph analytics. Another dimension that is central to our research is the highly dynamic nature of graph data. Social, web, transaction, and epidemiological networks are constantly evolving, thus necessitating that analytics be updated accordingly. Our goal in this research is to introduce methods and techniques to manage large-scale graph data under realistic conditions of heterogeneity, dynamicity, and impreciseness of information. Our main objective is to achieve scalability of fundamental analytics on big social and web graphs. We are particularly interested in analytics pertaining to (a) community discovery in social and other networks, (b) mining diversity in communities of heterogeneous networks, (c) mining and updating influential communities, (d) facilitation of the diffusion of good information as well as the removal of harmful misinformation. In contrast to other works, we aim at addressing complex, large scale graphs that continually evolve over time. As such, our algorithms will be fully dynamic and address the inherent temporality present in the aforementioned networks. We will address both atomic and batch type of updates, each with their own challenges and applications. We anticipate that our research will bring new insights and efficiency in a multitude of applications, such as social network utilization, knowledge graph analytics, biological network studies, epidemics evaluation, and so on. Understanding the structure of communities in large heterogeneous and dynamic graphs is an important part of the quest for providing computational insights to these applications. We expect our methods and results to provide the computational means for a large body of research benefiting large and small organizations in the private and public sector.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-02987
Name nom
Thomo, Alex
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2710
Research subject group en
Information technology
Research subject group fr
Information systems design
Research subject en
Technologie de l'information
Research subject fr
Conception de systèmes d'information
Application title
Community-Centric Mining of Large-Scale Dynamic Graphs
Keyword
algorithms for large graphs; community discovery in social networks; dynamic graph algorithms; graph-structured data; intelligent datacentric systems; massive and distributed data; social networks
Application summary
Graphs are ubiquitous and the most natural representation for many real world data coming from web, social, and knowledge networks, communication networks, transaction networks, and epidemiological networks. They are growing at an unprecedented rate. For instance, the web graph consists of more than a trillion websites, and the social graphs of Facebook, Twitter, and Weibo, have billions of users with many friend/follow connections per user. Consequently, storing such graphs and answering queries, mining patterns, and producing insights are becoming very challenging. These graphs also come with complex and diverse types on their nodes and edges which can represent people, items, and their interactions making for truly heterogeneous information networks. Furthermore, the information can be imprecise and uncertain, thus necessitating a probabilistic reasoning on the data. Not only is there a pressing need for new algorithms to handle these complex graph datasets, but scalability has to be addressed from the ground up to serve the real needs of organizations for industrial strength graph analytics. Another dimension that is central to our research is the highly dynamic nature of graph data. Social, web, transaction, and epidemiological networks are constantly evolving, thus necessitating that analytics be updated accordingly. Our goal in this research is to introduce methods and techniques to manage large-scale graph data under realistic conditions of heterogeneity, dynamicity, and impreciseness of information. Our main objective is to achieve scalability of fundamental analytics on big social and web graphs. We are particularly interested in analytics pertaining to (a) community discovery in social and other networks, (b) mining diversity in communities of heterogeneous networks, (c) mining and updating influential communities, (d) facilitation of the diffusion of good information as well as the removal of harmful misinformation. In contrast to other works, we aim at addressing complex, large scale graphs that continually evolve over time. As such, our algorithms will be fully dynamic and address the inherent temporality present in the aforementioned networks. We will address both atomic and batch type of updates, each with their own challenges and applications. We anticipate that our research will bring new insights and efficiency in a multitude of applications, such as social network utilization, knowledge graph analytics, biological network studies, epidemics evaluation, and so on. Understanding the structure of communities in large heterogeneous and dynamic graphs is an important part of the quest for providing computational insights to these applications. We expect our methods and results to provide the computational means for a large body of research benefiting large and small organizations in the private and public sector.
University of Victoria - $48,000 Grant (2023-24) | Canada Spends