MCSN Thursday, 15-Sep-11

From CCE wiki archived
Jump to: navigation, search

Today's assignment

Read sections 1.3.3 to 1.5; submit 1.6; come to class prepared with a Pajek example drawn from the Web, and illustrating chapter content.

Note: This will be a regular Thursday assignment (though we won't have time to look at everyone's examples each week). This week, the ESNAP readings focussed on a directed graph, so any directed graph from the web is fine. For instance, you could extract a portion of "following" relations, or look at musician relations (influences, influenced by) on The point is to create a directed graph in Pajek.

By the way,it's no secret: ESNAP contains answers to its Exercises and Questions (but not Assignments). The goal is learning. Please work the exercises and questions without looking at the answers. Then check your own work.

Note: you should be trying all the texts' examples using Pajek. If you're using the book edition of Pajek, everything should work exactly as the authors claim. The only limitation is that some of the right-click techniques don't work on the Mac.

Renaming file extensions

Whether you're working on a PC or Mac, you need to be able to edit Pajek files and modify their extensions (usually to .net, .clu, or .vec)

Operating systems like to hide these extensions (they think they're being nice). But you need to see them. Here's how.

Question of the day

  • Definition: Combinatorics: counting the number of structures with particular properties. (e.g. the number of different connected, undirected, simple graphs on 4 vertices)
  • Definition: Isomorphic = essentially the same. Non-isomorphic = "essentially different"
    • Isomorphic graphs contain the same connection information, even if they "look" different due to positioning or labelling of vertices.
    • Formally: two graphs are isomorphic if (and only if) we can pair their vertices such that two vertices are connected in one graph if (and only if) their pairs are connected in the other.
    • For example:
      • Energizing graphs in Pajek always generates an isomorphic equivalent
      • a square and a trapazoid and a twisted square graph are all isomorphic (all are cyclic graphs on 4 vertices)
      • all cyclic graphs on n vertices are isomorphic
      • a fully connected graph on 4 vertices (complete graph) represented as a square, or as a triangle with vertex in the center.
      • all complete graphs on n vertices are isomorphic
      • consider the 6 essentially different connected graphs on 4 vertices (11 if we allow disconnection)

  • Question: What is the relevance of graph combinatorics to the cross-cultural study of musical groups? What might be revealed by an investigate of the relation between non-isomorphic graph types, and the musical, interpersonal dynamics of performance, or musical success (measured in any number of ways: critical acclaim, celebrity, etc.)?

Brainstorming continues...

Data collection in SNA & class survey

  • Assembling a social network
    • Subjective measures via questioning
      • Free recall vs roster
      • Restricted choices vs. unrestricted choices
      • ranking vs. weighting
    • Objective measures via observation
      • Degree of interaction
      • Where people sit
      • Data on emails sent
      • Facebook friends
      • Genealogies
  • Data collection for assignment 1.7 (due Tuesday): design a quick survey collecting network data (ask one question only) and pass it round the class.

Homework exercises from Tuesday - review

Nuts-and-bolts: how to create networks in Pajek

  • Creating and manipulating networks in Pajek itself
  • Editing Pajek files in a text processor
    • Edge and arc list formats
    • Matrix format
  • Using txt2pajek
  • Using a programming language (e.g. scripting language such as php, perl, etc.) to generate Pajek files

More combinatorics...

  • How many lines does a complete simple graph on n vertices contain?
    • Undirected graphs
    • Directed graphs
  • How many undirected simple graphs are there on n vertices, when vertices are labelled?
  • How many essentially different (non-isomorphic) undirected simple graphs are there on n vertices?


  • Attributes and Relations. Read 2.1-2.4; submit 1.7.