By Kevin J. Lang (auth.), Konstantin Avrachenkov, Debora Donato, Nelly Litvak (eds.)

This publication constitutes the refereed lawsuits of the sixth foreign Workshop on Algorithms and versions for the Web-Graph, WAW 2009, held in Barcelona, Spain, in February 2009 - co-located with WSDM 2009, the second one ACM overseas convention on net seek and information Mining.

The 14 revised complete papers provided have been rigorously reviewed and chosen from a variety of submissions for inclusion within the booklet. The papers handle a wide selection of subject matters concerning the research of the Web-graph reminiscent of theoretical and empirical research of the net graph and internet 2.0 graphs, random walks on the internet and net 2.0 graphs and their functions, and layout and function overview of the algorithms for social networks. The workshop papers were certainly clustered in 3 topical sections on graph types for complicated networks, pagerank and net graph, and social networks and search.

Show description

Read or Download Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedings PDF

Best computers books

CAAP '90: 15th Colloquium on Trees in Algebra and Programming Copenhagen, Denmark, May 15–18, 1990 Proceedings

This quantity includes the lawsuits of the 15th Colloquium on timber in Algebra and Programming. The papers chosen current new learn effects and canopy the next themes: - Logical, algebraic and combinatorial houses of discrete buildings (strings, bushes, graphs, and so forth. ), together with the idea of formal languages regarded as that of units of discrete buildings and the idea of rewriting structures over those gadgets.

Performance Evaluation: Origins and Directions

This monograph-like state of the art survey provides the historical past, the main principles, the luck tales, and destiny demanding situations of functionality evaluate and demonstrates the impression of functionality overview on numerous assorted components via case experiences in a coherent and entire method. major researchers within the box have contributed 19 cross-reviewed topical chapters adequately overlaying the entire diversity of functionality evaluate, from theoretical and methodological concerns to functions in different different fields.

Developing Enterprise Java Applications with J2EE(TM) and UML

This e-book has an outstanding bankruptcy four on UML-Java mapping that's defined very basically. different books has a tendency to be bombastic and theorectical and vomitting out dry, dead excessive point UML jargons. considering that such a lot builders understands attrbutes and strategies larger than say, attempting to determine what an organization hyperlink is, the pointed out bankruptcy is helpful.

Additional resources for Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedings

Example text

WAW 2009, LNCS 5427, pp. 25–37, 2009. c Springer-Verlag Berlin Heidelberg 2009 26 R. Andersen and K. Chellapilla The complexity of identifying dense subgraphs can vary greatly when additional constraints on the size of the subgraph are introduced. Finding the densest subgraph with an arbitrary number of vertices is known as the densest subgraph problem ds, and can be solved exactly in polynomial time by solving a sequence of maximum flow problems [15,13]. The algorithm of Kortsarz and Peleg [18] produces a (1/2)-approximation of the densest subgraph in linear time, which is useful for graphs where the time required to compute maximum flows is prohibitively large.

Identifying subgraphs with high density is a useful primitive, which has been applied to find web communities, produce compressed representations of graphs, and identify link spam [9,14,20,8]. Effective heuristics have been developed to identify various kinds of dense subgraphs. Kumar et al. gave an algorithm for finding bipartite cliques [20]. Dourisboure et al. gave a scalable heuristic for finding small dense communities in web graphs [9]. The algorithm of Gibson et al. [14] finds dense communities using two-level min-hashing, with the goal of identifying link spam.

Then |Γ G (v) ∩ S| = 1∗S Aev . We have v∈T dv |Γ G (v) ∩ S|2 = dv 1∗S Aev e∗v A1S = 1∗S ADT A1S . v∈T Here DT = v∈T dv ev e∗v is the diagonal matrix with degree entry at vertex in T and 0 else where. We have v∈T dv |Γ G (v) ∩ S|2 − vol(S)2 vol3 (T ) vol(G)2 1 1∗ dd∗ DT dd∗ 1S | vol(G)2 S 1 ≤ |1∗S ADT A1S − 1∗ dd∗ DT A1S | vol(G) S 1 1 +| 1∗S dd∗ DT A1S − 1∗ dd∗ DT dd∗ 1S | vol(G) vol(G)2 S = |1∗S ADT A1S − 1 1 1 1 = |1S D 2 (I − L − ϕϕ∗ )D 2 DT A1S | 1 1 1 1∗ dd∗ DT D 2 (I − L − ϕϕ∗ )D 2 1S | +| vol(G) S 1 1 ≤ |1S D 2 (I − L − ϕ∗ ϕ)D 2 DT D 2 (I − L − ϕϕ∗ )D 2 1S | 1 1 1 1∗ dd∗ DT D 2 (I − L − ϕϕ∗ )D 2 1S | +2| vol(G) S ≤ σ 2 vol(S) max{d2v } + 2σ v∈T vol(S)3 vol5 (T ) .

Download PDF sample

Rated 4.81 of 5 – based on 22 votes