 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
|
|||||||||||||
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|||
 |
 |
 |
 |
|
||||||||||
 |
|
|||||||||||||
 |
|
|||||||||||||
 |
 |
|
||||||||||||
| Seminar Schedule (Seminar Organizer: Prof. Ziv Bar-Joseph) | |
Machine Learning Lunch Seminar
|
Spring 2008 Seminar
Date: April 17, 2008 Time: 12:00 PM - 1:00 PM Location: 5409 Wean Hall Speaker: Hanghang Tong Ph.D. Candidate Title: Center-Piece Subgraphs: Problem Definition and Fast Solutions Abstract: Given Q nodes in a social network (say, authorship network), how can we find the node/author that is the centerpiece, and has direct or indirect connections to all, or most of them? For example, this node could be the common advisor, or someone who started the research area that the Q nodes belong to. Isomorphic scenarios appear in law enforcement (find the master-mind criminal, connected to all current suspects), gene regulatory networks (find the protein that participates in pathways with all or most of the given Q proteins), viral marketing and many more. Connection subgraphs is an important first step, handling the case of Q=2 query nodes. Then, the connection subgraph algorithm finds the b intermediate nodes, that provide a good connection between the two original query nodes. Here we generalize the challenge in multiple dimensions: First, we allow more than two query nodes. Second, we allow a whole family of queries, ranging from ’OR’ to ’AND’, with ’softAND’ in-between. Finally, we design and compare a fast approximation, and study the quality/speed trade-off. We also present experiments on the DBLP dataset. The experiments confirm that our proposed method naturally deals with multi-source queries and that the resulting subgraphs agree with our intuition. Wall-clock timing results on the DBLP dataset show that our proposed approximation achieve good accuracy for about 6:1 speedup.
