Measuring and extracting proximity in networks

ABSTRACT

Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting proximity in networks called "cycle free effective conductance"(CFEC). Our proximity measure can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficien talgorithm. Also, we report experimental results and show examples for three large network data sets: a telecommunications calling graph, the IMDB actors graph, and an academic co-authorship network.

REFERENCES

• 1: A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, October 1999.
• 2: Indrajit Bhattacharya , Lise Getoor, Relational clustering for multi-type entity resolution, Proceedings of the 4th international workshop on Multi-relational mining, p.3-12, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1090193.1090195]
• 3: B. Bollobas. Modern Graph Theory. Springer-Verlag, 1998.
• 4: U. Brandes and D. Fleischer. Centrality measures based on current flow. In Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05), pages 533--544. LNCS 3404, Springer-Verlag, 2005.
• 5: Jonathan D. Cohen, Drawing graphs to convey proximity: an incremental arrangement method, ACM Transactions on Computer-Human Interaction (TOCHI), v.4 n.3, p.197-229, Sept. 1997 [doi>10.1145/264645.264657]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: DBLP computer science bibliography. dblp.uni-trier.de.
• 8: P. G. Doyle and J. L. Snell. Random Walks and Electrical Networks. The Mathematical Association of America, 1984. http://arxiv.org/abs/math.PR/0001057.
• 9: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 10: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 13: E. Hadjiconstantinou and N. Christofides. An efficient implementation of an algorithm for finding k shortest simple paths. Networks, 34:88--101, 1999.
• 14: Internet Movie Database. www.imdb.com.
• 15: M. M. John Hershberger and S. Suri. Finding the k shortest simple paths: A new algorithm and its implementation. In Proc. 5th Workshop on Algorithm Engineering and Experimentation (ALENEX '05), pages 26--36. SIAM, 2003.
• 16: N. Katoh, T. Ibaraki, and H. Mine. An efficient algorithm for k shortest simple paths. Networks, 12:411--427, 1982.
• 17: K. Lang. Finding good nearly balanced cuts in power law graphs. Technical report, Yahoo Research Labs, 2004.
• 18: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 19: A. Popescul and L. H. Ungar. Statistical relational learning for link prediction. In Proc. Workshop on Learning Statistical Models from Relational Data (IJCAI '03), 2003.
• 20: W. E. Winkler. The state of record linkage and current research problems. Technical report, Statistical Research Division, U.S. Bureau of the Census, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Human Factors

Keywords:
connection subgraph, cycle-free escape probability, escape probability, proximity, proximity subgraph, random walks