%0 Conference Paper %1 citeulike:246445 %A Faloutsos, Christos %A Mccurley, Kevin S. %A Tomkins, Andrew %B KDD '04: Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining %C New York, NY, USA %D 2004 %I ACM Press %K clustering findingcommunities skillinference socialnets community %P 118--127 %R 10.1145/1014052.1014068 %T Fast discovery of connection subgraphs %U http://dx.doi.org/10.1145/1014052.1014068 %X We define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. The primary motivation for this work is to provide a paradigm for exploration and knowledge discovery in large social networks graphs. We present a formal definition of this problem, and an ideal solution based on electricity analogues. We then show how to accelerate the computations, to produce approximate, but high-quality connection subgraphs in real time on very large (disk resident)graphs. We describe our operational prototype, and we demonstrate results on a social network graph derived from the World Wide Web. Our graph contains 15 million nodes and 96 million edges, and our system still produces quality responses within seconds. %@ 1581138889

@inproceedings{citeulike:246445, abstract = {We define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. The primary motivation for this work is to provide a paradigm for exploration and knowledge discovery in large social networks graphs. We present a formal definition of this problem, and an ideal solution based on electricity analogues. We then show how to accelerate the computations, to produce approximate, but high-quality connection subgraphs in real time on very large (disk resident)graphs. We describe our operational prototype, and we demonstrate results on a social network graph derived from the World Wide Web. Our graph contains 15 million nodes and 96 million edges, and our system still produces quality responses within seconds.}, added-at = {2006-06-16T10:34:37.000+0200}, address = {New York, NY, USA}, author = {Faloutsos, Christos and Mccurley, Kevin S. and Tomkins, Andrew}, biburl = {https://www.bibsonomy.org/bibtex/245766409ac4e1d7c9d156e26cae14d87/ldietz}, booktitle = {KDD '04: Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining}, citeulike-article-id = {246445}, comment = {Connection Subgraph Problem Given: an edge-weighted undirected graph G, vertices s and t from G, and an integer budget b Find: a connected subgraph H containing s and t and at most b other vertices1 that maximizes a “goodness” function g(H). Sub-problem 1: What function g is an appropriate “goodness”? Sub-problem 2: How can the subgraph H maximizing g be found quickly? --- The goodness function g(H)that we propose is exactly the total delivered current that the chosen subgraph H carries from source to sink, after the repeated taxations by the universal sink z. We are now faced with the problem of finding good connection subgraphs under that measure. We can reduce the problem to that of calculating the currents on the original graph, followed by a process that extracts a subgraph that carries high current to t. We refer to the latter problem as that of display generation, and we discuss it in detail in Section 4.1. Calculating current flows with a universal sink is feasible even for very large graphs, but not in an interactive environment. In order to address this problem, we propose an optional preprocessing step, called candidate generation. The idea is to quickly produce a moderate-sized graph, by removing nodes and edges that are too remote from s and t to influence the solution. In our interactive system, this is what allows us to produce good connection subgraphs within a few seconds. We describe the candidate generation process in Section 4.2. --- Task: Extract a Copnnection Subgraph that "explains" how two nodes relate to each other. Method: greedily add s-t connections with highest flow per capita (flow capacity / number of new vertices) Uses a precalcupation for candidate selection: Expand neighborhoods from s and t until the graphes merge. Data: WWW Domain: extract named-entity ("how close do names occur on websites?")}, doi = {10.1145/1014052.1014068}, interhash = {9868008566d6fe69b042e9ea75df32b2}, intrahash = {45766409ac4e1d7c9d156e26cae14d87}, isbn = {1581138889}, keywords = {clustering findingcommunities skillinference socialnets community}, pages = {118--127}, priority = {4}, publisher = {ACM Press}, timestamp = {2006-06-16T10:34:37.000+0200}, title = {Fast discovery of connection subgraphs}, url = {http://dx.doi.org/10.1145/1014052.1014068}, year = 2004 }