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.