Result: On finding common neighborhoods in massive graphs

Title:
On finding common neighborhoods in massive graphs
Authors:
BUCHSBAUM, Adam L, GIANCARLO, Raffaele, WESTBROOK, Jeffery R
Source:
Theoretical computer science. 299(1-3):707-718
Publisher Information:
Amsterdam: Elsevier, 2003.
Publication Year:
2003
Physical Description:
print, 27 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Probabilités et statistiques, Probability and statistics, Statistiques, Statistics, Lois de probabilités, Distribution theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Recherche information. Graphe, Information retrieval. Graph, Borne inférieure, Lower bound, Cota inferior, Graphe orienté, Directed graph, Grafo orientado, Informatique théorique, Computer theory, Informática teórica, Méthode Monte Carlo, Monte Carlo method, Método Monte Carlo, Théorie graphe, Graph theory, Teoría grafo, Algorithme randomisé, Randomized algorithm, Algorithme échantillonnage, Sampling algorithm, Graphe massif, Massive graph, Voisinage commun, Common neighbourhood, Vecindad
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
AT&TLabs, Shannon Laboratory, 180 Park Avenue, Florham Park NJ 07932, United States
Dipartimento di Matematica ed Applicazioni, Universitá di Palermo, Via Archirafi 34, 90123 Palermo, Italy
4031 South Hempstead Circle, San Diego, CA 92116, United States
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=14668423
Rights:
Copyright 2003 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.14668423
Database:
PASCAL Archive

Further Information

We consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must sample almost every pair of vertices for their respective common neighborhoods.