The FYP has been finish. The total project is divided into two parts. We first developed a web-based system named "C-Explorer" as proposed. After that, we continued to study the problem of edge-attributed community search problem and designed a corresponding algorithm for retriving edge-attributed communities.
Community search algorithms, which aim to find the most likely community containing the query node, have been one of the hottest research topics in graph mining. To facilitate community search algorithms, we have proposed C-Explorer, which has the following functions:
• Enables users to formulate community search queries to retrieve and view communities which they are interested in.
• Compares the efficiency of different community search algorithms.
• Supports attributed graphs, in which each vertex in attributed graphs is associated with a set of attributes. C-Explorer can help to look for attributed communities, in which vertices are cohesive both structurally and semantically.
• Provides interfaces are provided for researchers to plug in different algorithms for testing or visualization.
Exploration
The “Exploration” page is for formulating attributed community search queries and viewing the communities returned.
• The left panel is for query formulation and the user interface is designed specifically for
community search queries. After specifying the query names, degree and the set of attributes, users can click on the “Search” button at the bottom to send the query to the server.
• If the “Reset” button is clicked, the query names and attributes will be deleted to start a new search. The resulting communities will be displayed in the right panel of the page.
• The “Theme” section at the top shows the set of attributes that all vertex share and it should be a subset of the attributes specified by the user in the query.
• If the result contains more than one community, users can choose to view different communities by clicking on the community at the bottom.
The layout of “Analysis” (see Figure 2.2) is similar to that of “Exploration”.
Because some of the community search algorithms do not support more than one query vertex, only one query name can be inputted. Once the text field loses its focus, the keywords of the name in the text field will be loaded and users can click on the “Compare” button after the selection of keywords.
Two metrics (CMF and CPJ) are used to evaluate the overall effectiveness of algorithms. The two metrics are considered effective in measuring the cohesiveness of a community in [1]. Usually, communities with better cohesiveness will score higher in these two metrics. The result is put into two charts and shown in the upper half of the right section(see Figure 2.2). The statistics of each algorithm are shown in the table under “Community Statistics” for users to check and compare.
The previous attributed-community search problem treat attributes as the characteristic of vertices. However, in social networks these characteristics are often reflected by interactions between users. Hence we propose to explore the possibility of retriving communities based on edge-attributes.
We modified the ACQ algorithm to solve the edge-attributed community search problem. The details of methodology, implementation and results can be found in the final report.
1 October 2017 |
Deliverables of Phase 1 (Inception) • Detailed project plan • Project web page |
22 October 2017 |
Solve Efficiency problem of the program and deploy the program
with ACQ embedded online |
November 2017 |
Design and testing of APIs for researchers to plugin algorithms
and datasets; Do literature collection and review of CR algorithms. |
December 2017 |
Learn about key concepts and related algorithms in CR algorithms. |
8-12 January 2018 |
First presentation |
21 January 2018 |
Deliverables of Phase 2 (Elaboration) • Preliminary implementation • Detailed interim report |
January – February 2018 |
Design and test the algorithm |
March – 15 April 2018 |
Combine the algorithm with the program for demonstration, write
reports about the algorithm. |
15 April 2018 |
Deliverables of Phase 3 (Construction) • Finalized tested implementation • Final report |
16-20 April 2018 |
Final presentation |
2 May 2018 |
Project exhibition |