"Querying Intimate-Core Groups in Weighted Graphs" wins Best Student Paper Award at IEEE ICSC 2017

The paper Querying Intimate-Core Groups in Weighted Graphs, co-authored by ISI Foundation post-doc Cigdem Aslay of the Algorithmic Data Analytics Lab, in collaboration with researchers from the University of British Columbia, Hong Kong Baptist University, Shenzhen University, Tamkang University, and NEC Corporation, won the "Best Student Paper Award" at the 11th IEEE International Conference on Semantic Computing in San Diego, California.

Within community detection – the task of identifying all communities in a given network – the research deals with the novel problem of querying intimate-core groups in weighted graphs: the intimate-core group of a given set Q of query nodes is defined as the most semantically intimate community that contains Q. Given a weighted undirected graph G, in which the edge weights denote the semantic distance between the nodes, a set Q of query nodes, and a positive integer k, the problem studied requires to find a densely connected subgraph of G in which each node has at least k neighbors, and the sum of weights on its edges is minimum among all such subgraphs.

Researchers develop efficient algorithms based on several practical heuristic strategies to enhance the retrieval efficiency. Extensive experiments are conducted on real-world datasets to evaluate efficiency and effectiveness of proposed algorithms. The results highlighted in the paper confirm that this new intimate-core group model outperforms state-of-the-art models in weighted graphs, opening several interesting avenues for future work in community search, a fundamental problem in network science that has many important real-world applications in broad areas such as content recommendation, finding groups in collaboration or protein-interaction networks, infectious disease control, and marketing.

The paper was presented at the 11th IEEE International Conference on Semantic Computing in San Diego, California ( http://icsc.eecs.uci.edu/2017/ ).