2010 TheCommunitySearchProblemandhow
- (Sozio et al., 2010) ⇒ Mauro Sozio, and Aristides Gionis. (2010). “The Community-search Problem and how to plan a Successful Cocktail Party.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835923
Subject Headings:
Notes
- Categories and Subject Descriptors: H.2.8 Database Management: Database Applications — Data mining; G.2.2 Discrete Mathematics: Graph Theory — Graph algorithms
- General Terms: Algorithms, Experimentation, Theory
Cited By
- http://scholar.google.com/scholar?q=%22The+community-search+problem+and+how+to+plan+a+successful+cocktail+party%22+2010
- http://portal.acm.org/citation.cfm?id=1835923&preflayout=flat#citedby
Quotes
Author Keywords
Graph mining, community detection, social networks, graph algorithms
Abstract
A lot of research in graph mining has been devoted in the discovery of communities. Most of the work has focused in the scenario where communities need to be discovered with only reference to the input graph. However, for many interesting applications one is interested in finding the community formed by a given set of nodes. In this paper we study a query-dependent variant of the community-detection problem, which we call the community-search problem: given a graph [math]\displaystyle{ G }[/math], and a set of query nodes in the graph, we seek to find a subgraph of [math]\displaystyle{ G }[/math] that contains the query nodes and it is densely connected.
We motivate a measure of density based on minimum degree and distance constraints, and we develop an optimum greedy algorithm for this measure. We proceed by characterizing a class of monotone constraints and we generalize our algorithm to compute optimum solutions satisfying any set of monotone constraints. Finally we modify the greedy algorithm and we present two heuristic algorithms that find communities of size no greater than a specified upper bound. experimental evaluation on real datasets demonstrates the efficiency of the proposed algorithms and the quality of the solutions we obtain.
References
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2010 TheCommunitySearchProblemandhow | Mauro Sozio Aristides Gionis | The Community-search Problem and how to plan a Successful Cocktail Party | KDD-2010 Proceedings | http://research.yahoo.com/files/kdd2010.pdf | 10.1145/1835804.1835923 | 2010 |