MCSN Thursday, 15-Sep-11

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. This will be a regular Thursday assignment. 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 Twitter.com "following" relations, or look at musician relations (influences, influenced by) on allmusic.com. 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. Submit your homework (I know you can get them all right if you look at the answers, but I want to see where people need help). Then check your own work.

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: "Different" = non-isomorphic
  • Isomorphic graphs contain the same connection information, even if the "look" different.
  • 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.
  • E.g.: a square and a trapazoid and a twisted square graph are all isomorphic
  • Energizing graphs in Pajek always generates an isomorphic equivalent

• 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 dynamics of performance?

Brainstorming continues...

• More precipitation from your brainstorms

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 different undirected simple graphs are there on n vertices?
    • numbers
    • pictures