NDLI: Extraction and classification of dense implicit communities in the Web graph

Please wait, while we are loading the content...

Extraction and classification of dense implicit communities in the Web graph

Content Provider	ACM Digital Library
Author	Dourisboure, Yon Geraci, Filippo Pellegrini, Marco
Copyright Year	2009
Abstract	The World Wide Web (WWW) is rapidly becoming important for society as a medium for sharing data, information, and services, and there is a growing interest in tools for understanding collective behavior and emerging phenomena in the WWW. In this article we focus on the problem of searching and classifying $\textit{communities}$ in the Web. Loosely speaking a community is a group of pages related to a common interest. More formally, communities have been associated in the computer science literature with the existence of a locally dense subgraph of the Web graph (where Web pages are nodes and hyperlinks are arcs of the Web graph). The core of our contribution is a new scalable algorithm for finding relatively dense subgraphs in massive graphs. We apply our algorithm on Web graphs built on three publicly available large crawls of the Web (with raw sizes up to 120M nodes and 1G arcs). The effectiveness of our algorithm in finding dense subgraphs is demonstrated experimentally by embedding artificial communities in the Web graph and counting how many of these are blindly found. Effectiveness increases with the size and density of the communities: it is close to 100% for communities of thirty nodes or more (even at low density). It is still about 80% even for communities of twenty nodes with density over 50% of the arcs present. At the lower extremes the algorithm catches 35% of dense communities made of ten nodes. We also develop some sufficient conditions for the detection of a community under some local graph models and not-too-restrictive hypotheses. We complete our Community Watch system by clustering the communities found in the Web graph into homogeneous groups by topic and labeling each group by representative keywords.
Starting Page	1
Ending Page	36
Page Count	36
File Format	PDF
ISSN	15591131
e-ISSN	1559114X
DOI	10.1145/1513876.1513879
Volume Number	3
Issue Number	2
Journal	ACM Transactions on the Web (TWEB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-04-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Web graph Communities Detection of dense subgraph
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

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

Extraction and classification of dense implicit communities in the web graph

Extraction and classification of dense communities in the web

WWW 2007 / Track: Search Session: Web Graphs Extraction and Classification of Dense Communities in the Web ∗

Dense Subgraph Extraction with Application to Community Detection

Predicting Edge Signs in Social Networks Using Frequent Subgraph Discovery

Fast and Compact Web Graph Representations

Unified Photo Enhancement by Discovering Aesthetic Communities From Flickr

Characterizing a national community web

The Web as a graph: How far we are

Extraction and classification of dense implicit communities in the Web graph

Similar Documents

Extraction and classification of dense implicit communities in the web graph

Extraction and classification of dense communities in the web

WWW 2007 / Track: Search Session: Web Graphs Extraction and Classification of Dense Communities in the Web ∗

Dense Subgraph Extraction with Application to Community Detection

Predicting Edge Signs in Social Networks Using Frequent Subgraph Discovery

Fast and Compact Web Graph Representations

Unified Photo Enhancement by Discovering Aesthetic Communities From Flickr

Characterizing a national community web

The Web as a graph: How far we are

Extraction and classification of dense implicit communities in the Web graph