Student research opportunities
Finding Close Communities in Large-Scale Networks
Project Code: CECS_821
This project is available at the following levels:
Honours, Summer Scholar, Masters, PhD
Keywords:
Algorithm design and analysis, graph problems, k-connectivity, dense subgraph finding, data processing in large data set, graph database, big data
Supervisor:
Assoc Professor Weifa LiangOutline:
Recent research suggests that most of real-world networks organise themselves into communities. Community structures have been found in social and biological networks, as well as technological networks such as the Internet. Automatically discovering such structures is fundamentally important for a better understanding of the relationships between network structures and functions. It will help the prediction of the evolution and growth of communities, and the study of their interactions. It may also help the observation of the ideology of a community, and the flow of ideas between communities. Discovering communities enables us to observe community-wide sentiment, and to study the degree to which a community’s sentiment influences each of its members. It has many practical applications. For example, identifying communities from a collaboration network may reveal scientific activities as well as evolution and development of research areas, detecting hidden communities on the web may help prevent crime and terrorism, and finding recreational communities may assist product marketing. Once a community is found, further investigation on the community is then possible, such as community outlier detection for finding interesting points or rising stars in the community.
This project is funded by the ARC Discovery, and will be co-supervised with the other two researchers: Prof. Chengfei LIU at Swinburne University of Technology and Prof Jeffrey X. YU at Chinese Hong Kong University.
Goals of this project
This project aims to develop effective models to represent communities and efficient approaches to discover communities. We will first investigate the rich semantics inherent in a community so as to model the community effectively. We will then develop efficient algorithms to dynamically maintain the discovered communities, and to discover communities using materialised views of network database. Finally, we will build up a prototype to justify our study of communities, to test and demonstrate the effectiveness of the models and efficiency of the algorithms developed.
Requirements/Prerequisites
Excellent programing skills, database knowledge, algorithm design and analysis, graph algorithm
