Hypertext '08: Session 3: Social Linking II: Analysis and Modeling

Chair: Andreas Hotho (Universität Kassel, Germany)

The Very Small World
of the Well-Connected (Long Paper)
Xiaolin Shi, Matthew Bonner, Lada
Adamic and Anna Gilbert

Matt Bonner is the presenter; this paper won a “best paper” award at the banquet last night.

Vertex Important Graph Synopsis. (Promises a definition!)

Opening
image — “Network or Hairball?” Huge networks are difficult to study
and share. To shrink or summarize a network, you create a subgraph of
vertices you decide are important. Study these important vertices, and
compare their behavior to the rest of the graph.

Degree,
betweenness, closeness, PageRank.  He’s spending time describing in
detail all the importance measures. Assortativity vs
disassortativity… [The graphs of “betweenness” and “PageRank” look
very similar, which I gather is because Google bases its linking
algorithim on betweenness.]

Demonstrated how subgraphs can
differ greatly based on which importance factor your subgraph selects
for. [To translate into my discipline, I suppose this is a close
reading of a small portion of a text, by blocking out all the
information you don’t want to find.]

Leass than 10% of the nodes are needed before the subgraph results look very close to the overall dataset. 

This
is the third time the presenter has apologized because a dotted red
line is invisible in the slides being projected. His oral explanation
of what he lines should signify is clear enough, I gather, though he’s
referring to special kinds of graphs that network researchers (not I)
would be expected to understand.

A blog aggregator in his
dataset was connecting to many, many nodes, not just the most important
nodes, so there’s a notable anomaly in degree. [I’m actually intersted
in this, though he’s mentioned it only as a footnote and offered to say
more on it during the Q & A if desired.]

[“NP-complete:
reducible to Steiner…” nope, the slide changed even before I could
write this down as an example of a statement that’s perfectly
straightforward but requires background knowledge that I would need to
look up. I missed what “Keep One” and “Keep All” mean.]

[What
I’m getting out of this is a mathematical illustration of the thesis
that it is possible to gain useful, accurate information from a study
of a subset within a dataset, and that other factors (which are over my
head) seem to control for whatever bias you introduce when you select a
set of nodes for a particular characteristic. Unlike the “close
reading” metaphor I used earlier, if you know what you’re doing, you
can select a “synopsis” that emphasizes the features you wish to study,
and identify how closely your subset matches the overall dataset’s
similar features.]

An Epistemic Dynamic
Model for Tagging Systems (Long Paper)
Klaas Dellschaft and Steffen
Staab

Klaas
pressented, beginning with a basic introduction of tagging [probably
not necessary for this audience, but it was brief and… and I don’t
mind an introduction that gives me a minute or so to adjust to a new
speaker’s cadence, accent, and relationship to the visuals.]

How do users influence each other in tagging systems?

User
interface, user brain, background knowledge, and “something else” all
influence tagging behavior.  We can only observe the tagging behavior
[well, we can learn something about the user interface, too, but I
think that comment is intended to contrast with the inscrutability of
the brain.]

Klass introduces foksonomy, [again I would assume
most in the audience already know the term, but I’m always intersted in
how individual scholars define their terms… this is necessary in the
humanities, since we don’t always have empirical evidence to help us
define our terms.]

Presented sample of coding mechanism
“co-ocurrence stream” .  Measured how many occurrences, how many users,
how many different texts, and how many resources.

After 100
occurrences of a term, you have about 50 texts.  The number of distinct
texts is growing but the rate of growth decreases… it’s a nice
logarhithmic scale showing that each time the tag appears again, it is
more likely that the tag is used on an existing text, rather than a new
text.

The frequency of texts is inverted — The most often used
text has a 4-5% probability, text #100 was 01.% probability. [Did he
describe that as “fat tail distribution”?  I assume that’s the
oppossite of the “long tail”?]  Not quite as even as the tag graph, but

Resource streams [I missed something… does this mean he’s
graphing the channel by which the document is delivered, or by which
the tag entered into his dataset, or the timeline of each entry in his
dataset regardles of source or other characteristics? He briefly went
through some related research, so obviously this is a common concept
that I would know about if I knew the literature.  The whole idea of
measuring the time between the creation of links is an exciting new
concept for me, since it blends well with composition pedagogy that
considers writing as process rather than product.]

[Equation
that I can’t type fast enough] Probability of selecting from background
knowledge — probability of selecting word w for topic t modeled by —
[drat the slide changed.]

[Another equation] probabilty of repeating a previous tag assignment.

Now he’s finished presenting the model, and he’s moving on to compare the observed behavior with the behavior he modeled.

[I’m
starting to pick up on the biological metaphors — mutating of tag
assignments, limited number of texts in the pool.  I hadn’t realized
just how deeply the “virus” metaphor is rooted in this subject
matter… Does the metaphor drive the science? Are there patterns that
don’t already have known biological instances that aren’t pursued
because there isn’t already a vocabulary to describe them?  I’m going
to have to re-read The Selfish Gene for all the parts that I skimmed
over when I was reading it simply to undersand “meme”.]

After
more than 1000 tag assignments, the frequency of assignments is more or
less stable. There’s a drop around tag number 7 in resource streams. 
Cited http://isweb.uni-koblenz.de/Research/Tagdataset and
http://tagora-project.edu

First question, from the conference
host, was about whether the user interface affects tagging behavior?
[Here I am, thinking that I’m an idiot, and a big-shot followed up on
something that dimly appeared to my Humanities brain. I confess I
didn’t follow the answer but that’s my fault — I was high-fiving
myself for having wondered about that earlier.]

Understanding the
Efficiency of Social Tagging Systems using Information Theory (Long Paper)
Ed H. Chi and Todd
Mytkowicz

Todd
presented. Organization of knowledge… the printing press was “a
start” at organizing human knowledge. [Well… the codex, the classical
form of the argument, rhyme, abstract thought… but I digress.]

Great–
Todd notes that the audience doesn’t need an introduction to tagging,
but notes the value of communicating the way he frames tagging. We all
have individualistic motivations for tagging, but the result is a
global knowledge map; the research posits that tags create a
lower-dimensional representation of the material the tags describe.

This
is a distributive process with hundreds and thousands of users, and
trying to infer high-level behavior is challenging.  If we sample
del.icio.us data, we don’t own access to the entire dataset, and
therefore don’t know whether we’re sampling the data accurately. Noted
the Measure/Model/Innovate cycle, and indicated roadblocks when you’re
measuring a dataset that you don’t own.

Information theory — how much information do tags tell us about an underlying document.

Entropy
measures the uncertainty in a dataset. A heterogenous set has maximun
entropy at log n, minimum of 0. You can increase entropy by increasing
the number of things in your dataset; or you can keep n constant and
make data more uniform [did he mean to say less uniform?]

[I lost track for a while because my blog was having trouble saving…  picking back up]

Overview of the data collected from deli.cio.us over about 120 weeks. The number of documents increases rapidly… there have to be many tags for every individual document that comes into the system.

Entropy of the document set is rising… the diversity of the document set is increasing over time. People are creating new content for the system, rather than re-enforcing opinions that have already been entered into the system. This is good for del.icio.us in the long term.

Tagging in delicious is both encoding and retrieving. Encoding — users have some notion of document space and future use; how likely are you to use a document in the future? We’re sending a message to ourself in the future that we’re going to have to retrieve. [How intersting — this concept might be very useful in getting students to think about the value of taking notes in class or annotating their journey through a challenging academic or literary text.]

Around week 80, there’s a dramatic stabilization of the entropy curve. The number of tags are increasing over time. People are becoming more and more likely to set up a tag that’s already in the document space. [What happened around that time to create that change? Did some blogging tool or some content site like Wired add “delicious” tags to its content?] 

Tag “efficiency” is decreasing — crested around week 40.  Tags are becoming less and less signficant. The descriptive power of English is limited.

Do people change their behaviors to re-capture some of that efficiency? People are starting to add more tags to each item in response to the navigation pressure. Ziff’s principle of least effort. If you are just archiving a document, you probably won’t put much effort into the tagging.  Putting the notion of tagging in to the framework of information theory.

[My observation… the delicious interface changes over time, so the nature of tagging changes over time.]

Rather than delicious suggesting tags others have used, try asking the user to come up with new tags [as Google does in its picture-tagging game].

[During the Q and A I asked whether the drop at week 80 was realted to a change in the del.icio.us interface, but Todd says not. They did notice other phenomena that corresponded with changes in the user interface.]