NDLI: Degree and similarity based search in networks

Content Provider	IEEE Xplore Digital Library
Author	Bin Wu Qing Ke Yuxiao Dong
Copyright Year	2011
Description	Author affiliation: School of Computer Science, Beijing University of Posts and Telecommunications, China (Bin Wu; Qing Ke; Yuxiao Dong)
Abstract	Decentralized search in networks is an important algorithmic problem in the study of complex networks and graph mining. It has a large number of practical applications, including shortest paths search in social network relationship, web pages search in WWW, querying files in peer-to-peer file sharing networks and so on. In this paper, we present a probabilistic analysis of this search problem that produces a surprisingly simple and effective method. Based on the analysis, we introduce a new decentralized search strategy named Product Search. In this strategy, for every step we forward the message to the neighbor with the minimum product of neighbor's degree and common neighbors' size. We compare this strategy with other common strategies like degree-based search, random walk and breadth-first search. And the results show that the product search outperforms others. We also find that the degree-based search does not do well in high clustering power-law networks, and traditional graph statistical properties such as average path length and skewed degree distribution fail to fully explain the level of search-ability in a network.
Starting Page	1267
Ending Page	1270
File Size	135076
Page Count	4
File Format	PDF
ISBN	9781612841809
e-ISBN	9781612841816
DOI	10.1109/FSKD.2011.6019636
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-07-26
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Graph Mining Peer to peer computing Social network services Similarity Degree Complex networks Search problems Probabilistic logic Electronic mail Decentralized Search Algorithm Physics
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient Search in Networks Using Conductance

A multidimensional heuristic for social routing in peer-to-peer networks

Expansion and search in networks

SPUN: A P2P Probabilistic Search Algorithm Based on Successful Paths in Unstructured Networks

Information Flow and Search in Unstructured Keyword Based Social Networks

Fast Search to Detect Communities by Truncated Inverse Page Rank in Social Networks

Improved Search Algorithm Based on Probability of Node's Degree on Complex Networks

A searching algorithm based on Markov transition matrix in WSN

Update Management in Decentralized Social Networks

Degree and similarity based search in networks

Similar Documents

Efficient Search in Networks Using Conductance

A multidimensional heuristic for social routing in peer-to-peer networks

Expansion and search in networks

SPUN: A P2P Probabilistic Search Algorithm Based on Successful Paths in Unstructured Networks

Information Flow and Search in Unstructured Keyword Based Social Networks

Fast Search to Detect Communities by Truncated Inverse Page Rank in Social Networks

Improved Search Algorithm Based on Probability of Node's Degree on Complex Networks

A searching algorithm based on Markov transition matrix in WSN

Update Management in Decentralized Social Networks

Degree and similarity based search in networks