| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

The Davalos Affair For Idiots; Not The Onion: Google Fireside Chat w Kissinger; Bicycle Wheels, Inertia, and Energy; Another Tax Fraud; Google's Borg; A Verion That Redirects To Local HTTP Server; Spanish Accents For Idiots; Aluminium Cans; Advice on Spray Painting; Female View of Online Chat From a Male; UX Reading List; S4 Subgroups - Geometric Interpretation; Fucking Email; The SQM Affair For Idiots; Using Kolmogorov Complexity; Oblique Strategies in bash; Curses Tools; Markov Chain Monte Carlo Without all the Bullshit; Email Para Matias Godoy Mercado; The Penta Affair For Idiots; Example Code To Create numpy Array in C; Good Article on Bias in Graphic Design (NYTimes); Do You Backup github?; Data Mining Books; SimpleDateFormat should be synchronized; British Words; Chinese Govt Intercepts External Web To DDOS github; Numbering Permutations; Teenage Engineering - Low Price Synths; GCHQ Can Do Whatever It Wants; Dublinesque; A Cryptographic SAT Solver; Security Challenges; Word Lists for Crosswords; 3D Printing and Speaker Design; Searchable Snowden Archive; XCode Backdoored; Derived Apps Have Malware (CIA); Rowhammer - Hacking Software Via Hardware (DRAM) Bugs; Immutable SQL Database (Kinda); Tor GPS Tracker; That PyCon Dongle Mess...; ASCII Fluid Dynamics; Brandalism; Table of Shifter, Cassette and Derailleur Compatability; Lenovo Demonstrates How Bad HTTPS Is; Telegraph Owned by HSBC; Smaptop - Sunrise (Music); Equation Group (NSA); UK Torture in NI; And - A Natural Extension To Regexps; This Is The Future Of Religion; The Shazam (Music Matching) Algorithm; Tributes To Lesbian Community From AIDS Survivors; Nice Rust Summary; List of Good Fiction Books; Constructing JSON From Postgres (Part 2); Constructing JSON From Postgres (Part 1); Postgres in Docker; Why Poor Places Are More Diverse; Smart Writing on Graceland; Satire in France; Free Speech in France; MTB Cornering - Where Should We Point Our Thrusters?; Secure Secure Shell; Java Generics over Primitives; 2014 (Charlie Brooker); How I am 7; Neural Nets Applied to Go; Programming, Business, Social Contracts; Distributed Systems for Fun and Profit; XML and Scheme; Internet Radio Stations (Curated List); Solid Data About Placebos; Half of Americans Think Climate Change Is a Sign of the Apocalypse; Saturday Surf Sessions With Juvenile Delinquents; Ssh, tty, stdout and stderr; Feathers falling in a vacuum; Santiago 30m Bike Route; Mapa de Ciclovias en Santiago; How Unreliable is UDP?; SE Santiago 20m Bike Route; Cameron's Rap; Configuring libxml with Eclipse; Reducing Combinatorial Complexity With Occam - AI; Sentidos Comunes (Chilean Online Magazine); Hilary Mantel: The Assassination of Margaret Thatcher - August 6th 1983; NSA Interceptng Gmail During Delivery; General IIR Filters; What's happening with Scala?; Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!

© 2006-2015 Andrew Cooke (site) / post authors (content).

Flattening Graphs

From: andrew cooke <andrew@...>

Date: Mon, 28 Mar 2011 06:46:16 -0300

When you construct a graph of relationships you often have a rather vague /
flexible notion of "relatedness".  It's natural to use this to decide who are
neighbours, and even to weight the edges.  But it also leads to a curious
problem when you start to use the graph.

The problem is that some nodes come out "better" than others.  You can play
around with how you calculate your "relatedness factor", but the natural
result of any flexible measurement is a degree of inequality.

This can lead to bias.  For example, in the case of Uykfe (and Uykfd before),
I construct a graph of related musicians and then use that to generate
playlists of related tracks.  The "better" nodes tend to capture the playlist
(I imagine that you could relate this to eigenvectors of a transition matrix
or something similar?).

For example, Sparklehorse had links out to various artists, but the highest
weighted links from those neighbours went elsewhere.  So my playlist, when it
starts at Sparklehorse, never returns.

My natural response to this is to make the graph undirected.  But this doesn't
help - it turns out not of the links from Sparklehorse are that great, so
neighbours still prefer other nodes.

A simple solution (one I reinvented for Uykfe after using it in Uykfd and then
forgetting) is to restrict the number of links for each node to some fixed
amount (note: not a cutoff by weight, but a fixed number) and then ignore
weights in transitions.

This doesn't completely remove the problem - the "best" nodes now have more
connections that the "worst" - but it does level the playing field a little.

(I haven't yet tried weighting the notes out from nodes by the inverse of the
number of links at the target).

Andrew

Active Flattening

From: andrew cooke <andrew@...>

Date: Fri, 1 Apr 2011 08:58:02 -0300

Just to follow up on this, the latest (final?) version of Uykfe does actively
flatten graphs: it initially generates 10 outgoing edges per node.  Then it
identifies nodes with the most incoming edges and deletes the loweest weighted
edges that contribute to that.  It's not a perfect solution (you have to stop
when you hit some minimum number of outgoing edges in the neighbours), but it
helps.

Andrew

Comment on this post