Measuring and extracting proximity graphs 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). Importantly, the measured proximity is accompanied with a proximity subgraph which allows assessing and understanding measured values. Our proximity calculation can handle more than two endpoints, directed edges, is statistically well behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficient algorithm to measure and extract proximity. Also, we report experimental results and show examples for four large network datasets: a telecommunications calling graph, the IMDB actors graph, an academic coauthorship network, and a movie recommendation system.

REFERENCES

• 1: Barabasi, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Sci. 286, 509--512.
• 2: Robert Bell , Yehuda Koren , Chris Volinsky, Modeling relationships at multiple scales to improve accuracy of large recommender systems, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281206]
• 3: 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]
• 4: Bollobas, B. 1998. Modern Graph Theory. Springer.
• 5: Brandes, U. and Fleischer, D. 2005. Centrality measures based on current flow. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3404, Springer, 533--544.
• 6: 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]
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: dblp. 1998. DBLP computer science bibliography. dblp.uni-trier.de.
• 9: Doyle, P. G. and Snell, J. L. 1984. Random Walks and Electrical Networks. Mathematical Association of America. http://arxiv.org/abs/math.PR/0001057.
• 10: 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]
• 11: 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]
• 12: 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
• 13: 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]
• 14: Hadjiconstantinou, E. and Christofides, N. 1999. An efficient implementation of an algorithm for finding k shortest simple paths. Netw. 34, 88--101.
• 15: imdb. 2007. Internet Movie Database. www.imdb.com.
• 16: John Hershberger, J. M. M. and Suri, S. 2003. Finding the k shortest simple paths: A new algorithm and its implementation. In Proceedings of the 5th Workshop on Algorithm Engineering and Experimentation (ALENEX). SIAM, 26--36.
• 17: Katoh, N., Ibaraki, T., and Mine, H. 1982. An efficient algorithm for k shortest simple paths. Netw. 12, 411--427.
• 18: Yehuda Koren , Stephen C. North , Chris Volinsky, Measuring and extracting proximity in networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150432]
• 19: Lang, K. 2004. Finding good nearly balanced cuts in power law graphs. Tech. Rep., Yahoo Research Labs.
• 20: 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]
• 21: Myers, C. L., Robson, D., Wible, A., Hibbs, M. A., Chiriac, C., Theesfeld, C. L., Dolinski, K., and Troyanskaya, O. G. 2005. Discovery of biological networks from diverse functional genomic data. Genome Biol. 6, R114.
• 22: netflix. 2007. Netflix prize. www.netflixprize.com.
• 23: Popescul, A. and Ungar, L. H. 2003. Statistical relational learning for link prediction. In Proceedings of the Workshop on Learning Statistical Models from Relational Data (IJCAI).
• 24: Ruslan Salakhutdinov , Andriy Mnih , Geoffrey Hinton, Restricted Boltzmann machines for collaborative filtering, Proceedings of the 24th international conference on Machine learning, p.791-798, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273596]
• 25: Tenenbaum, J. B., de Silva, V., and Langford, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Sci. 290, 2319--2323.
• 26: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150448]
• 27: Winkler, W. E. 1999. The state of record linkage and current research problems. Tech. Rep., Statistical Research Division, U.S. Bureau of the Census.

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, graph mining, proximity, proximity subgraph, random walk