%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.02", %%% date = "07 August 2013", %%% time = "10:13:04 MDT", %%% filename = "lncs2009a.bib", %%% University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "32435 458 2296 22113", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "BibTeX; bibliography; Lecture Notes in %%% Computer Science", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a bibliography of papers published in %%% Lecture Notes in Computer Science %%% (Springer-Verlag) for 2009. %%% %%% Bibliography entries below treat the series %%% as a journal, rather than as conference %%% proceedings. %%% %%% The companion bibliography lncs.bib lists %%% just the individual volumes in the series, %%% and the lncs19xy*.bib files list individual %%% papers for year 19xy. The large number of %%% papers in this collection, and limitations %%% in TeX and BibTeX, and in WWW HTTP transfer %%% speeds, necessitate the splitting of the %%% papers bibliographies into yearly files. %%% %%% At version 1.02, the year coverage looked %%% like this: %%% %%% 2009 ( 9) %%% %%% InProceedings: 5 %%% Proceedings: 4 %%% %%% Total entries: 9 %%% %%% This bibliography has been constructed %%% primarily from the publisher Web site. %%% Regrettably, final page numbers are not %%% available at that source. %%% %%% Numerous errors in the sources noted above %%% have been corrected. Spelling has been %%% verified with the UNIX spell and GNU ispell %%% programs using the exception dictionary %%% stored in the companion file with extension %%% .sok. %%% %%% BibTeX citation tags are uniformly chosen as %%% name:year:abbrev, where name is the family %%% name of the first author or editor, year is a %%% 4-digit number, and abbrev is a 3-letter %%% condensation of important title words. %%% Citation labels were automatically generated %%% by software developed for the BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order, with the help of ``bibsort %%% -byvolume''. The bibsort utility is available %%% from ftp.math.utah.edu in /pub/tex/bib. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{ "\ifx \undefined \bbb \def \bbb #1{\mathbb{#1}} \fi" # "\ifx \undefined \circled \def \circled #1{(#1)}\fi" # "\ifx \undefined \mathbb \def \mathbb #1{{\bf #1}}\fi" # "\ifx \undefined \mathcal \def \mathcal #1{{\cal #1}}\fi" # "\ifx \undefined \mathrm \def \mathrm #1{{\rm #1}}\fi" # "\ifx \undefined \ocirc \def \ocirc #1{{\accent'27#1}}\fi" # "\ifx \undefined \reg \def \reg {\circled{R}}\fi" # "\ifx \undefined \TM \def \TM {${}^{\sc TM}$} \fi" # "\hyphenation{ Ay-ka-nat Giun-chi-glia Lakh-neche Mal-er-ba Mart-el-li Reut-e-nau-er Thiel-sch-er }" } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb= "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-LECT-NOTES-COMP-SCI= "Lecture Notes in Computer Science"} %%% ==================================================================== %%% Publisher abbreviations: @String{pub-SV= "Springer-Verlag Inc."} @String{pub-SV:adr= "New York, NY, USA"} %%% ==================================================================== %%% Series abbreviations: @String{ser-LNAI= "Lecture Notes in Artificial Intelligence"} @String{ser-LNCS= "Lecture Notes in Computer Science"} %%% ==================================================================== %%% Bibliography entries: @InProceedings{Alam:2009:FPC, author = "Md. Hijbul Alam and Jongwoo Ha and Sangkeun Lee", editor = "Anonymous", booktitle = "Proceedings of the 14th International Conference on Database Systems for Advanced Applications", title = "Fractional {PageRank} Crawler: Prioritizing {URLs} Efficiently for Crawling Important Pages Early", volume = "5463", publisher = pub-SV, address = pub-SV:adr, pages = "590--594", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-00887-0_52", ISBN = "3-642-00886-0", ISBN-13 = "978-3-642-00886-3", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "????", bibdate = "Sat May 8 18:33:10 MDT 2010", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, abstract = "Crawling important pages early is a well studied problem. However, the availability of different types of framework for publishing web content greatly increases the number of web pages. Therefore, the crawler should be fast enough to prioritize and download the important pages. As the importance of a page is not known before or during its download, the crawler needs a great deal of time to approximate the importance to prioritize the download of the web pages. In this research, we propose Fractional PageRank crawlers that prioritize the downloaded pages for the purpose of discovering important URLs early during the crawl. Our experiments demonstrate that they improve the running time dramatically while crawling the important pages early.", acknowledgement = ack-nhfb, } @InProceedings{Chen:2009:SNE, author = "Wei Chen and Shang-Hua Teng and Yajun Wang and Yuan Zhou", title = "On the $ \alpha $-sensitivity of {Nash} equilibria in {PageRank}-based network reputation games", crossref = "Deng:2009:FAT", volume = "5598", pages = "63--73", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-02270-8_9", ISBN = "3-642-02269-3", ISBN-13 = "978-3-642-02269-2", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "????", MRclass = "68Wxx", bibdate = "Sat May 8 18:33:10 MDT 2010", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, ZMnumber = "05578464", abstract = "Web search engines use link-based reputation systems (e.g. PageRank) to measure the importance of web pages, giving rise to the strategic manipulations of hyperlinks by spammers and others to boost their web pages' reputation scores. Hopcroft and Sheldon [10] study this phenomenon by proposing a network formation game in which nodes strategically select their outgoing links in order to maximize their PageRank scores. They pose an open question in [10] asking whether all Nash equilibria in the PageRank game are insensitive to the restart probability $ \alpha $ of the PageRank algorithm. They show that a positive answer to the question would imply that all Nash equilibria in the PageRank game must satisfy some strong algebraic symmetry, a property rarely satisfied by real web graphs. In this paper, we give a negative answer to this open question. We present a family of graphs that are Nash equilibria in the PageRank game only for certain choices of $ \alpha $.", acknowledgement = ack-nhfb, } @InProceedings{Chung:2009:LGP, author = "Fan Chung", title = "A Local Graph Partitioning Algorithm Using Heat Kernel {PageRank}", crossref = "Avrachenkov:2009:AMW", pages = "62--75", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-540-95995-3_6", ISBN = "3-540-95994-7", ISBN-13 = "978-3-540-95994-6", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "????", MRclass = "68M10", bibdate = "Sat May 8 18:33:04 MDT 2010", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, ZMnumber = "05505865", abstract = "We give an improved local partitioning algorithm using heat kernel pagerank, a modified version of PageRank. For a subset S with Cheeger ratio (or conductance) h, we show that there are at least a quarter of the vertices in S that can serve as seeds for heat kernel pagerank which lead to local cuts with Cheeger ratio at most {$ O(\sqrt {h}) $}, improving the previously bound by a factor of {$ \sqrt {log|S|} $}.", acknowledgement = ack-nhfb, } @InProceedings{Jager:2009:PSH, author = "Douglas V. Jager and Jeremy T. Bradley", editor = "Anonymous", booktitle = "Proceedings of the 2nd International Conference on Theory of Information Retrieval: Advances in Information Retrieval Theory", title = "{PageRank}: Splitting Homogeneous Singular Linear Systems of Index One", volume = "5766", publisher = pub-SV, address = pub-SV:adr, pages = "17--28", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-04417-5_3", ISBN = "3-642-04416-6", ISBN-13 = "978-3-642-04416-8", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "????", bibdate = "Sat May 8 18:33:09 MDT 2010", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, abstract = "The PageRank algorithm is used today within web information retrieval to provide a content-neutral ranking metric over web pages. It employs power method iterations to solve for the steady-state vector of a DTMC. The defining one-step probability transition matrix of this DTMC is derived from the hyperlink structure of the web and a model of web surfing behaviour which accounts for user bookmarks and memorised URLs. \par In this paper we look to provide a more accessible, more broadly applicable explanation than has been given in the literature of how to make PageRank calculation more tractable through removal of the dangling-page matrix. This allows web pages without outgoing links to be removed before we employ power method iterations. It also allows decomposition of the problem according to irreducible subcomponents of the original transition matrix. Our explanation also covers a PageRank extension to accommodate TrustRank. In setting out our alternative explanation, we introduce and apply a general linear algebraic theorem which allows us to map homogeneous singular linear systems of index one to inhomogeneous non-singular linear systems with a shared solution vector. As an aside, we show in this paper that irreducibility is not required for PageRank to be well-defined.", acknowledgement = ack-nhfb, } @InProceedings{Litvak:2009:CTD, author = "Nelly Litvak and Werner Scheinhardt and Yana Volkovich and Bert Zwart", title = "Characterization of Tail Dependence for In-Degree and {PageRank}", crossref = "Avrachenkov:2009:AMW", pages = "90--103", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-540-95995-3_8", ISBN = "3-540-95994-7", ISBN-13 = "978-3-540-95994-6", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "????", bibdate = "Sat May 8 18:33:10 MDT 2010", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, abstract = "The dependencies between power law parameters such as in-degree and PageRank, can be characterized by the so-called angular measure, a notion used in extreme value theory to describe the dependency between very large values of coordinates of a random vector. Basing on an analytical stochastic model, we argue that the angular measure for in-degree and personalized PageRank is concentrated in two points. This corresponds to the two main factors for high ranking: large in-degree and a high rank of one of the ancestors. Furthermore, we can formally establish the relative importance of these two factors.", acknowledgement = ack-nhfb, keywords = "Multivariate extremes; PageRank; Power law graphs; Regular variation", } %%% ==================================================================== %%% Cross-referenced entries must come last; they are sorted in volume %%% order with ``bibsort --byseriesvolume'': @Proceedings{Avrachenkov:2009:AMW, editor = "Konstantin E. Avrachenkov and Debora Donato and Nelly Litvak", booktitle = "{Algorithms and models for the web-graph: 6th international workshop, WAW 2009 Barcelona, Spain, February 12--13, 2009 proceedings}", title = "{Algorithms and models for the web-graph: 6th international workshop, WAW 2009 Barcelona, Spain, February 12--13, 2009 proceedings}", volume = "5427", publisher = pub-SV, address = pub-SV:adr, pages = "x + 183", year = "2009", ISBN = "3-540-95995-5, 3-540-95994-7 (softcover)", ISBN-13 = "978-3-540-95995-3, 978-3-540-95994-6 (softcover)", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "QA76.9.A43 W39 2009", bibdate = "Thu May 6 17:32:37 MDT 2010", bibsource = "felix.us.ohio-state.edu:210/INNOPAC; z3950.loc.gov:7090/Voyager", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, acknowledgement = ack-nhfb, } @Proceedings{Allen:2009:CSIa, editor = "Gabrielle Allen and Jaros{\l}aw Nabrzyski and Edward Seidel and Geert Dick van Albada and Jack Dongarra and Peter M. A. Sloot", booktitle = "{Computational science -- ICCS 2009. 9th international conference Baton Rouge, LA, USA, May 25--27, 2009. Proceedings, Part I}", title = "{Computational science -- ICCS 2009. 9th international conference Baton Rouge, LA, USA, May 25--27, 2009. Proceedings, Part I}", volume = "5544", publisher = pub-SV, address = pub-SV:adr, year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-01970-8", bibdate = "Sat Sep 4 17:11:27 2010", bibsource = "ftp://ftp.math.utah.edu/pub/bibnet/authors/d/dongarra-jack-j.bib", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, ZMnumber = "1162.68300", acknowledgement = ack-nhfb, classmath = "{*68-06 (Proceedings of conferences (computer science)) 00B25 (Proceedings of conferences of miscellaneous specific interest) }", remark = "For the preceding conference see Zbl 1139.68300, Zbl 1139.68301 and Zbl 1139.68302. For Part II of the proceedings of ICCS 2009 see Zbl 1162.68302.", } @Proceedings{Allen:2009:CSIb, editor = "Gabrielle Allen and Jaros{\l}aw Nabrzyski and Edward Seidel and Geert Dick van Albada and Jack Dongarra and Peter M. A. Sloot", booktitle = "{Computational science -- ICCS 2009. 9th international conference Baton Rouge, LA, USA, May 25--27, 2009. Proceedings, Part II}", title = "{Computational science -- ICCS 2009. 9th international conference Baton Rouge, LA, USA, May 25--27, 2009. Proceedings, Part II}", volume = "5545", publisher = pub-SV, address = pub-SV:adr, pages = "xxxvii + 921", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-01973-9", bibdate = "Sat Sep 4 17:11:30 2010", bibsource = "ftp://ftp.math.utah.edu/pub/bibnet/authors/d/dongarra-jack-j.bib", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, ZMnumber = "1162.68302", acknowledgement = ack-nhfb, classmath = "*68-06 (Proceedings of conferences (computer science)) 00B25 (Proceedings of conferences of miscellaneous specific interest)", remark = "For the preceding conference see Zbl 1139.68300, Zbl 1139.68301 and Zbl 1139.68302. For Part II of the proceedings of ICCS 2009 see Zbl 1162.68301.", } @Proceedings{Deng:2009:FAT, editor = "Xiaotie Deng and John E. Hopcroft and Jinyun Xue", booktitle = "{Frontiers in algorithmics. Third international workshop, FAW 2009, Hefei, China, June 20--23, 2009. Proceedings}", title = "{Frontiers in algorithmics. Third international workshop, FAW 2009, Hefei, China, June 20--23, 2009. Proceedings}", volume = "5598", publisher = pub-SV, address = pub-SV:adr, pages = "xiv + 372", year = "2009", DOI = "http://dx.doi.org/10.1007/978-3-642-02270-8", ISBN = "3-642-02270-7, 3-642-02269-3", ISBN-13 = "978-3-642-02270-8, 978-3-642-02269-2", ISSN = "0302-9743 (print), 1611-3349 (electronic)", LCCN = "QA76.9.A43 F39 2009", bibdate = "Thu May 6 11:19:59 MDT 2010", bibsource = "z3950.gbv.de:20011/gvk", bibsource = "http://www.math.utah.edu/pub/tex/bib/lncs2009a.bib", series = ser-LNCS, URL = "http://www.springerlink.com/content/p1040n9jt618; http://www.zentralblatt-math.org/zmath/en/search/?an=1166.68003", acknowledgement = ack-nhfb, subject = "algorithms; computational complexity; computer communication networks; computer science; computer software; data mining; software engineering", xxeditor = "David Hutchison and Bernhard Steffen and Doug Tygar and Takeo Kanade and Josef Kittler and Jon M. Kleinberg and Friedemann Mattern and John C. Mitchell and Jinyun Xue and Oscar Nierstrasz and Madhu Sudan and John E. Hopcroft and Xiaotie Deng and Gerhard Weikum and Moshe Y. Vardi and C. {Pandu Rangan} and Demetri Terzopoulos and Moni Nao", }