Skip to content →

neverendingbooks Posts

the google matrix

Published January 16, 2004 by lievenlb

This morning there was an intriguing post on arXiv/math.RA
entitled A Note on
the Eigenvalues of the Google Matrix. At first I thought it was a
joke but a quick Google revealed that the PageRank algorithm really
is at the heart of Google technology, so I simply had to find out more
about it. An extremely readable account of it can be found in The PageRank Citation Ranking: Bringing Order to the Web which is really the
start of Google. It is coauthored by the two founders : Larry Page and
Sergey Brin. A quote from the introduction

“To test the utility of PageRank for search, we built a web
search engine called Google (Section
5)”

Here is an intuitive idea of
_PageRank_ : a page has high rank if the sum of the ranks of its
_backlinks_ (that is, pages linking to the page in question) is
high and it is computed by the _Random Surfer Model_ (see
sections 2.5 and 2.6 of the paper). More formally (at least from my
quick browsing of some papers, maybe the following account is slightly
erroneous and I’ll have to spend some more time reading) let
N be the number of webpages (estimated between 3 and 4
billion) and consider the N x N matrix
A the so called GoogleMatrix where 

A = cP  + (1-c)(v x
vec(1))

where P is the
column-stochastic matrix (meaning : all entries are zero or positive and
the sum of all entries in each column adds up to 1) with
entries

P(i,j) = 1/N(i) if i->j and 0
otherwise

where i and j are webpages and i->j
denotes that page i has a link to page j and where N(i) is the total
number of pages linked to in page i (all this information is available
once we download page i). c is a constant 0 < c < 1 and
corresponds to the fraction of webpages containing an _outlink (that
is, a link to another page) by all webpages (it seems that Google uses
c=0.85 as an estimate). Finally, v is a column vector with zero or
positive numbers adding up to 1 and vec(1) is the constant row vector
(1,…,1). The idea behind this term is that in the _Random Surfer
Model_ to compute the PageRank the Googlebot (normally following
links randomly in pages it enters) jumps every (1-c)x100% links randomly
to an entirely different webpage where the chance that it will end up at
page i is given by the i-th entry of v (this is to avoid being trapped
in a web-loop). So, in Googles model the bot _teleports_ itself
randomly every 6th link or so. Now, the PageRank is a
column-eigenvector for the GoogleMatrix A with eigenvalue 1 which can be
approximated by the RandomSurfer model and the rate of convergence of
this process depends on the _second_ largest eigenvalue for A
(the largest being 1). Now, in the paper posted this morning a simple
proof is given that this eigenvalue is c (because the matrix P has
multiple eigenvalues equal to 1). According to a previous paper on the
subject The
Second Eigenvalue of the Google Matrix, this statement has
implications for the convergence rate of the standard PageRank algorithm
as the web scales, for the stability of PageRank to perturbations to the
link structure of the web, for the detection of Google spammers, and for
the design of algorithms to speed up PageRank. But I’ll have to
read more to understand the Google spammers bit…

2 Comments

the cpu 2 generation

Published January 15, 2004 by lievenlb

Never
ever tell an ICT-aware person that you want to try to set up a
home-network before you understand all 65536 port-numbers and their corresponding
protocols. Here is what happened to me this week. Jan Adriaenssens returned from an extended vacation in New Zealand and I told him
about my problems with trying to set up WebDAV securely. He
stared at me with that look that teenage children have if they
find out their parents dont know how to handle the simplest things on a
mobile such as saving a number, writing an SMS let alone use the
dictionary… and asked ‘now why would you want to do that??? I just
use AppleTalk to connect to my computer securely’. Now I’m not such a
fool that I didnt try this out but I didnt manage to get matrix
mounted on my Desktop. ‘Oh, but thats probably because of the
firewall’ Jan said ‘just send an email to Peter (the guy running the
defenses here) and ask him to open up ports 548 and
427…’ And sure enough five minutes later the problem was
solved and I could trow my WebDAV-plans in the dustbin (although, I
think Ive found a use for WebDAV but will keep this a bit longer to
myself until I checked it out). If you think that was the end of it,
think twice. Never ever point an ICT-professional to your
computer. They then start looking at its firewall-logs and find all
sorts of things such as : ‘I noticed that traffic from port 53
was dropped to the firewall, could it be that you configured the
firewall as DNS-server. If this is the case, you better remove it and it
will increase your network-speed, I think.’ And sure enough that
IP-address was set on my machine as one of two possibilities for the
DNS-server so I quickly removed it and in the process thought that maybe
I should also remove the other one so I did send Peter another email
asking whether that was ok. It turned out that the second IP address was
the genuine DNS-server so I got a sec answer back ‘You better leave
this as it is otherwise not much will work…’ Oh, shame, shame eternal
shame on me!

My only defense is that I still belong
to what I would call the cpu 2 generation (I’m a few years too
old to belong to the more computer-aware generation X). When I
started out doing research in 1980 the single most important command was

cpu 2

which you had to type before you could run any program.
By typing this you asked to be given 2 minutes of central processing
time, so you had to write all your programs in such a way that either
they gave a result back within 2 minutes or to include lots of
output-commands giving you a chance to determine at which parameters you
would restart the program for your next cpu 2. I once computed in
this way all factorial maximal orders in quaternion algebras by spending
a couple of days in the computer room. These days any desktop computer
would finish this task in half a minute. Perhaps the younger generations
will appreciate all the hard computer-work we had to do back then if
they read a bit from the computer history museum page!

Leave a Comment

NOG master class

Published January 14, 2004 by lievenlb


Yesterday I made reservations for lecture rooms to run the
master class on non-commutative geometry sponsored by the ESF-NOG project. We have a lecture room on
monday- and wednesday afternoon and friday the whole day which should be
enough. I will run two courses in the program : non-commutative
geometry and projects in non-commutative geometry both 30
hours. I hope that Raf Bocklandt will do most of the work on the
Geometric invariant theory course so that my contribution to it
can be minimal. Here are the first ideas of topics I want to cover in my
courses. As always, all suggestions are wellcome (just add a
comment).

non-commutative geometry : As
I am running this course jointly with Markus Reineke and as Markus will give a
mini-course on his work on non-commutative Hilbert schemes, I will explain
the theory of formally smooth algebras. I will cover most of the
paper by Joachim Cuntz and Daniel Quillen “Algebra extensions and
nonsingularity”, Journal of AMS, v.8, no. 2, 1995, 251?289. Further,
I’ll do the first section of the paper by Alexander Rosenberg and Maxim Kontsevich,
“Noncommutative smooth spaces“. Then, I will
explain some of my own work including the “One
quiver to rule them all” paper and my recent attempts to classify
all formally smooth algebras up to non-commutative birational
equivalence. When dealing with the last topic I will explain some of Aidan Schofield‘s paper
“Birational classification of moduli spaces of representations of quivers“.

projects in
non-commutative geometry : This is one of the two courses (the other
being “projects in non-commutative algebra” run by Fred Van Oystaeyen)
for which the students have to write a paper so I will take as the topic
of my talks the application of non-commutative geometry (in particular
the theory of orders in central simple algebras) to the resolution of
commutative singularities and ask the students to carry out the detailed
analysis for one of the following important classes of examples :
quantum groups at roots of unity, deformed preprojective algebras or
symplectic reflexion algebras. I will explain in much more detail three talks I gave on the subject last fall in
Luminy. But I will begin with more background material on central simple
algebras and orders.

Leave a Comment

antwerp sprouts

Published January 13, 2004 by lievenlb

The
game of sprouts is a two-person game invented by John Conway and Michael Paterson in 1967 (for some
historical comments visit the encyclopedia). You just need pen and paper to
play it. Here are the rules : Two players, Left and Right, alternate
moves until no more moves are possible. In the normal game, the last
person to move is the winner. In misere play, the last person to move is
the loser. The starting position is some number of small circles called
“spots”. A move consists of drawing a new spot g and then drawing two
lines, in the loose sense, each terminating at one end at spot g and at
the other end at some other spot. (The two lines can go to different
spots or the same spot, subject to the following conditions.) The lines
drawn cannot touch or cross any line or spot along the way. Also, no
more than three lines can terminate at any spot. A spot with three lines
attached is said to be “dead”, since it cannot facilitate any further
action.

You can play sprouts online using this Java applet.
There is also an ongoing discussion about sprouts on the geometry math forum. Probably the most complete
information can be found at the world game
of sprouts association. The analysis of the game involves some nice
topology (the Euler number) and as the options for Left and Right are
the same at each position it is an impartial game and the outcome
depends on counting arguments. There is also a (joke) variation on the
game called Brussels sprouts (although some people seem to miss the point
entirely).

Some years ago I invented some variations
on sprouts making it into a partizan game (that is, at a given
position, Left and Right have different legal moves). Here are the rules
:

Cold Antwerp Sprouts : We start with n White
dots. Left is allowed to connect two White dots or a White and bLue dot
or two bLue dots and must draw an additional Red dot on the connecting
line. Right is allowed to connect two White dots, a Red and a White dot
or two Red dots and must draw an additional bLue dot on the connecting
line.

Hot Antwerp Sprouts : We start with n
White dots. Left is allowed to connect two White dots or a White and
bLue dot or two bLue dots and must draw an additional bLue dot on the
connecting line. Right is allowed to connect two White dots, a Red and a
White dot or two Red dots and must draw an additional Red dot on the
connecting line.

Although the rules look pretty
similar, the analysis of these two games in entirely different. On
february 11th I’ll give a talk on this as an example in
Combinatorial Game Theory. I will show that Cold Antwerp Sprouts
is very similar to the game of COL, whereas Hot Antwerp Sprouts resembles SNORT.

Leave a Comment

homemade .mac

Published January 12, 2004 by lievenlb

The
other members of my family don’t understand what I am trying to do the
last couple of days with all those ethernet-cables, airport-stations,
computer-books and the like. ‘Improving our network’ doesn’t make
much of an impression. To them, our network is fine as it is : from
every computer one has access to the internet and to the only
house-printer and that is what they want. To them, my
computer-phase is just an occupational therapy while recovering
from the flu. Probably they are right but I am obstinate in
experimenting to prove them wrong. Not that there is much hope,
searching the web for possible fun uses of home-networks does not give
that many interesting pages. A noteworthy exception is a series of four
articles by Alan Graham for the macdevcenter
on the homemade dot-mac with OS X-project.

In
the first article Homemade Dot-Mac with OS X he explains how to
set-up a house-network (I will give a detailed account of our
home-network shortly) and firing up your Apache webserver. One nice
feature I learned from this is to connect a computer by ethernet to the
router and via an Airport card to the network (you can force this by
specifying the order of active network ports in the
SystemPreferences/Network/Show Network port configuration-pane :
first Built-in Ethernet and second Airport). This way you
get a faster connection to the internet while still connecting to the
other computers on the network. In the second part he explains how to
get yourself a free domain name even if you have (as we do) a dynamic
IP-address via a service like DynDNS. Indeed it is quite easy to set this up but
so far I failed to reach my new DNS-server from outside the network,
probably because of bad port-mapping of my old isb2lan-router.
This afternoon I just lost two hours trying to fix this (so far :
failed) as I didn’t even know how to talk to my router as I lost the
manual which is no longer online. A few Google-searches further I
learned that i just had to type http://192.168.0.1 to get at the set-up pages
(there is even a hidden page) but you shouldnt try these links
unless you are connected to one of these routers. Maybe I will need
another look at this review.

In the second
article, Homemade Dot-Mac with OS X, Part 2 he discusses in
length setting up a firewall with BrickHouse (shareware costing $25) compared to the
built-in firewall-pane in SystemPreferences/Sharing convincing me
to stay with the built-in option. Further he explains what tools one can
use to set up a homepage (stressing the iPhoto-option).Finally, and this
is the most interesting part (though a bit obscure), he hints at the
possibility of setting up your own iDisk facility either using
FTP (insecure) or WebDAV.

The third article in the
series is Homemade Dot Mac: Home Web Radio in which he
claims that one can turn the standard OS X-Apache server into an iTunes
streaming server. He uses for this purpose the QuickTime Streaming Sever which you can get for
free from the Apple site but which I think works only when you have an
X-server. It seems that all nice features require an X-server so
maybe I should consider buying one…

The (so far)
final article is Six Great Tips for Homemade Dot Mac Servers is
really interesting and I will come back to most op these possibilities
when (if) I get them to work. The for me most promising options are :
the central file server (which he synchronizes using the
shareware-product ExecutiveSync ($15 for an academic license) but
I’m experimenting also a bit with the freeware Lacie-program Silverkeeper which seems to be doing roughly the
same things. The iTunes central-hack is next on my ToDo-list as
is (at a later stage) the WebDav and the Rendezvous-idea. So it seems
I’ll prolong my occupational therapy a while…

Leave a Comment

combinatorial game software

Published January 11, 2004 by lievenlb


As I am going to give a talk on Combinatorial Game Theory early
next month I have to update my rusty knowledge of canonical forms of
two-person game positions, their temperature theory and the like. As
most of the concepts in this field are recursive they are hard to work
out by humans but easy for computers. So it is nice to have a good
program to use. I remember that David Wolfe wrote a couple of years ago the Gamesman Toolkit but it seems he has taken it off
his website. Still, you can get it from the Software released by Michael Ernst page. So,
download the games.tar.gz-file and uncompress it on your Desktop.
Then do the following 

cd Desktop/games sudo make sudo cp
games /usr/bin/ /usr/bin/games

to get it up and
running (for documentation of how to use it see the Gamesman
Toolkit-paper above. But, it seems that as of July 2003 there is a much
better alternative around : the Combinatorial Game Suite of Aaron Siegel. It is an open source Java-program so it
runs on many platforms (including Mac OSX). Here is the way to get it
going : first download it and you will get a
cgsuite-0.4-folder on your desktop. Then type 

cd
Desktop/cgsuite-0.4 java -jar cgsuite.jar

and after a few
questions (including whether you want to be on the mailing list of the
project) the program starts up. It is very well documented with an
on-line manual which I have to read over the coming
days…

Leave a Comment

SSL on Mac OSX

Published January 10, 2004 by lievenlb

A
longer term project is to get the web-server www.matrix.ua.ac.be integrated in our home-network
as an external WebDAV-server (similar to the .Mac-service
offered by Apple). But as this server runs all information about the
master-class on non-comutative geometry connecting to it via HTTP to use
WebDAV is too great of a security risk as all username/password
combinations will be send without encryption. Hence the natural question
whether this server can be set up to run SSL (Secure Sockets
Layer) such that one can connect via HTTPS and all exchanged information
will be encrypted. As the server is an Apache it comes down to get
mod-ssl running. A Google on mod_ssl OS X gives the
ADC-document Using mod-ssl on Mac OS X which seems to be just
what I want. This page is very well documented giving detailed
instructions of using the openssl command. However, the
end-result is rather weak : it only makes the localhost running
HTTPS, that is, one can connect to your own computer safely… which is
pretty ridiculous (other computers in the same network cannot even
connect safely).

So, back to the Google-list on which
one link raises my interest Configuring mod-ssl on Mac OS X which looks like
the previous link but has one essential difference : the page is written
by Marc Liyanage. If you ever tried to get PHP and/or MySQL
running under OS X you will have noticed that his pages are by far the
most reliable on the subject, hence maybe he has also something
interesting to say on mod-ssl. However, the bottom line of the
document is not very promising :

You
should now be able to access the content with https://127.0.0.1 from
the same machine.

which is again the
localhost. So perhaps it is just impossible to run mod-ssl
without having an X-server. Anyway, let us try out his procedure.
Begin by issuing the following commands in the Terminal

sudo -s cd /etc/httpd mkdir ssl chmod 700 ssl cd
ssl gzip -c --best /var/log/system.log > random.dat openssl rand
-rand file:random.dat 0

Next, we need a server certificate. If you
want to do it properly you need a certificate from a certification
authority such as Thawte but this costs at least $200 a year which I
am not willing to pay. The alternative is to use a self-signed
certificate which will force the browser to display an error-message
but if the user dismisses it all traffic exchanged with the server will
still be encrypted which is just what I want. So, type the command

openssl req -keyout privkey-2001.pem -newkey rsa:1024
 -nodes -x509 -days 365 -out cert-2001.pem

(all on one line).
You will be asked a couple of questions (the only important one is the
Common Name (eg, YOUR name). Here you should take care to enter
the host name of your web server exactly as it will be used later in the
common name field. In my test-case, if I want to get my server
used by other computers in the network this name will be
imaclieven.local. (note the trailing .). Now issue the following
commands 

chmod 600 privkey-2001.pem chown root
privkey-2001.pem apxs -e -a -n ssl /usr/libexec/httpd/libssl.so

which will activate the SSL-module (if at a later state you want
to de-activate it you have to change -a by -A in the last command).
Finally, we have to change the /etc/httpd/httpd.conf file so
first save a backup-version and then add the following lines at the end
of the file : 

(IfModule mod-ssl.c)     Listen 80    
Listen 443     SSLCertificateFile /etc/httpd/ssl/cert-2001.pem    
SSLCertificateKeyFile /etc/httpd/ssl/privkey-2001.pem    
SSLRandomSeed startup builtin     SSLRandomSeed connect builtin   
 (VirtualHost -default- :443)         SSLEngine on    
(/VirtualHost) (/IfModule)

Observe that round brackets ()
should be replaced by <>. Finally, we do 

apachectl
stop apachectl start

and we are done! Going to another computer
in the network and typing in Safari https://imaclieven.local./
will result in an error message


Just click Continue and you will have a secure connection
to the server. Thanks Marc Liyanage!

(Added january
11th) Whereas the above allows one to make a HTTPS connection it is not
enough for my intended purposes. In order to get a secure connection to
a WebDAV server, this server must have the mod-auth-digest module
running which seems to be impossible for the standard Apache server of
10.3. You need an X-server to have this facility. So I think I have to
scale down my ambitions a bit.

Leave a Comment

one week blogging

Published January 9, 2004 by lievenlb

So far I
found it rather easy to post one or more messages a day as I was
installing a lot of software or trying to get things working and was
merely logging my progress for future reference. These notes are useful
to me but probably not to the rest of the world. Another thing I noticed
is that I’m using this blog sometimes as a replacement for my
Bookmarks, merely listing interesting web-pages without too much
personal comments. I will continue to post both install-logs and
bookmark-logs but in addition I want to write (say weekly) a lengthier
post on a specific topic with more background, more details (such as
screenshots) and more personal comments. We will see how this works out
in the coming weeks…

Another thing that slightly
worried me is that people visiting my homepage and clicking on to my
blog may expect entirely different things there. But this cant be
helped, I’m sitting on an OSX-cloud at the moment but no doubt this
will change quickly. Beginning of february I have to give a talk on
Combinatorial Game Theory and soon afterwards the
Non-commutative Geometry Master Class starts in which I’m giving
a couple of courses, so mathematics will become more dominant in this
blog from next month on…

On a
blog-tech matter : I found a quite good editor pMpost
which is meant to write pMachine-blogs offline and upload them by one
click. It also synchronizes categories etc. on login. Further, it has a
spelling-checker but the thing I really like about it is that you can
save texts as a draft and continue at a later time (sadly, it remember
the date/hour when you start your post so when you finally submit it it
will be posted at the starting- rather than the posting-day. Still,
there is nothing that copy/paste cannot solve. I hope to use this
facility when (read if) I’m going for a more in-depth post. Another
matter that I will address to as quickly as possible (probably over the
weekend) is teh layout of this site. The main annoying thing is that the
text doesnt resize when you increase/decrease window width. So I will
address this matter first and probably leave a personal layout and
color-scheme to later. Fortunately, I did find a good site containg a
lot of CSS templates for pMachine weblogs. Another site I’ll have to
investigate over the weekend is pMtemplates. But don’t expect too much from the
layout-side, I still have other projects to worry about : SSL, WebDAV,
streaming iTunes, getting on Ethernet-DVD player to work and so
on.

Leave a Comment

WarChalking

Published January 9, 2004 by lievenlb


What then is all this WarWalking, WarDriving,
WarChalking and so on? In particular, why the aggressive
War-word in them ? From what I learned, the historical origin of
these terms comes from the 1983 movie “War Games” in which a
kid sets up his modem to dial numbers until it finds a computer to hack
leading inevitably to the US-army in total panic. This hobby created the
phrase WarDialing. In analogy, a person driving around in a car
with a laptop in search for wireless networks is said to be
WarDriving, if (s)he is on foot it is clearly WarWalking.
Because of the aggressive nature of the War-subword some people have
re-engineered an explanation :

WAR = Wireless
Access Reconnaissance

so let us hope this acronym
will catch on. Now then, what is WarChalking ? It was invented by
Matt Jones and the idea is that a WarWalker should write a symbol in
chalk on the wall nearest to the discovered Access Point describing its
nature (see picture on the left) : the first sign depicts an open
node, the next a closed one and the last one is a node with
WEP-protection (btw. WEP=Wired Equivalent Privacy). A lot
of people seem to take this fairly serious, there is even a webpage warchalking.org devoted to it on which you can
find a lot more information. And as warchalking was originally British,
there had to be also an American site containing among other things a not
that active forum. Further, the unofficial HOW-TO of WarDriving may be
interesting. To me it all sounds as an excuse to buy a
GPS-receiver and a
laptop…

Leave a Comment

iMacBondiBlue

Published January 8, 2004 by lievenlb

We
still have an original iMac (Bondi Blue). It runs at 233 MHz,
has 192Mb RAM and a hard-disk of 4Gb, so is pretty outdated. Still, when
Mac OSX was introduced I had a hard time installing extra RAM in it (for
this model you have to take it apart disconnecting all sorts of cables)
so it would be a shame if this oldest member of the family is left out
of the network. The problem is that it has an Ethernet card but no
possibility to include an Airport-Card… So I bought a D-Link Wireless USB adapter and was told that installation would be
plug-and-play : just connect it to the USB-port, open up the
Applications/Utilities/Airport Setup Assistant and everything
would rum smoothly. Hahah! When I started the Assistant it was clever
enough to detect that no Airport-Card was installed and refused further
action. But, there is a CD in the package so I did install the driver
which really adds a new icon Wireless Adaptor to the System
Preferences. Clicking it gave the sobering message No Wireless
Device Attached and I couldnt press the Scan button for detection of
possible networks. But disconnecting the D-Link a number of times and
pressing it very hard eventually I got a wireless icon in the toolbar
but still it couldnt give me a signal strength of available networks.
But that might be right as the ABS is protected both by WEP and by
MAC-access. So, I added the MAC-address of the D-Link to the list in the
Access Control pane of the Airport Admin Utility which
also gives a way to get at the Hex-equivalent of the WEP-key : click on
the Password icon. So, i manually created in the Wireless
Adaptor-preferences a network with the correct name, WEP-key equivalent
and so on and thought that would do it. But no, now I did get a signal
strength but it showed that I was not connected and that the WEP-key was
incorrect. On the other hand, no complaints were listed when i tried to
access the ABS as Peer-to-peer but this created all other sorts
of problems as I could detect with iStumbler so I quickly removed
this option and got to bed.

This morning I realized
that I still have the old Graphite Airport Base Station lying
idle so I connected it with a patch cable to the Router, reconfigured it
without WEP-protection and without Access Control and instructed
BondiBlue to connect to this new network, which it immediately managed
to do but it took a few restarts and time to get it onto Internet and
connected to other computers on this second network. So, now I will
increase security on this new network and see where it fails. First, add
Access Control by including the MAC Address of the D-Link and other
computers, reconfigure the ABS and the BondiBlue is still on the
network! Next, WEP : in the Apple documentation it is mentioned to take
a passphrase of exactly 5 symbols to ‘increase compatibility with
third-party products’. Let’s try ab;12, change in the
Wireless Adaptor-Prefrences the properties of the network by
choosing Enable WEP 40 Bits ASCII (5 characters) and give the key
ab;12 and sure enough : everything works! So the problem was that
our regular network is WEP-protected by a longer passphrase and D-Link
could not handle the HEX-equivalent 10 digit number. A final attempt :
in the D-Link documentation a solution is offered by giving the ABS a
10-digit Hex together with a starting $-sign so let’s try
$4bb2603b52 on the ABS and 4bb2603b52 in the properties of
the D-Link preferences : success!

However, if I try
any of these two methods on the Airport Extreme base-station,
none of this works! If it were not for the USB-network printer on the
extreme ABS I would just replace it again with the Graphite. Still, I’m
fed up with it for today, BondiBlue is online but via Graphite and all
other computers can communicate with it when they change stations.

Leave a Comment