# MCSN Thursday, 13-Oct-11

*Helpful hints:*

1) Pajek data structures and tabular data

- Think of all vectors and partitions pertaining to a particular network as columns in a table or spreadsheet. The rows represent vertices, and each column contains properties for each vertex, either integer (partition) or real (vector) values.
- In Pajek we don't enter this table as a single data structure, but rather each column is treated separately. But you can create your dataset as a table, then cut and paste individual columns into separate files to create your partitions and vectors.
- When we extract a subnetwork based on a partition, we also need to extract from the other partitions and vectors. Hence:
**Partitions->extract second from first**, and**Vector->extract subvector**commands. These are equivalent to selecting rows using conditions on one table column (for instance, selecting all rows for which that column=1).

2) Your projects should not involve research with human subjects. Data will typically come from the web, though you could use other sources (e.g. a database, newspapers, etc.). But networks need not be purely "virtual" - for instance, consider the relation between performers, songs, festivals, and concert attendees.

---

**Cohesive subgroups**

- Find dense subnetworks.
- 100% dense subnetwork = complete network.
- But we can relax this condition and search for, say, 75% dense subnetworks.
- See example 6node.net
- Density of the whole?
- Identify 100% dense subnets (complete subnets)
- Identify 75% dense subnets
- Identify 50% dense subnets

- Find maximal dense subnetworks
- 100%: "clique". Identify cliques in 6node.net
- 70%: 'relaxed' clique, based on density.

- Find high degree subnetworks
- Find subnetworks containing minimal degree nodes. Problem: not necessarily connected! (e.g. hubs)
- k-core: require minimum degree
*within the subnet!*The k-core is a maximal subnetwork in which each vertex's degree is at least k. - how to find them? Pajek does this for you. But it's instructive to come up with an algorithm: Start with a node of minimal degree, add neighbors of minimal degree, and check if they can be admitted (perhaps by checking
*their*neighbors). Then maximize by checking which other vertices can be added, and iterate for those new vertices. let's do this for 6node.net - e.g. 0-core: all vertices
- e.g. 1-core: any vertex with at least one incident line, e.g. all vertices in this case.
- e.g. 2-core: start with E, add A, F; maximize by adding D, C, B
- e.g. 3-core: start with A, add C, F, D
- Note two important facts:
- For each k there is only ever
*one*k-core (by definition). - However, the k-core is not necessarily connected (we should subdivide by components)
- Each core contains a subnetwork, which is typically smaller than the whole
- The 1-core contains the 2-core, the 2-core contains the 3-core, etc. because the degree condition is "minimum". Generally: the k-core contains the k+1-core. We say the cores are
*nested*. - Therefore vertices can belong to multiple cores. When we want to create a partition, we assign each vertex to its highest core.
- Attiro: symmetrize, then run Net->partitions->core->all, then draw-partition. Then Operations->extract from network to examine only higher cores.

- For each k there is only ever

- Your web examples?

Now, back to cliques...

- A clique is a maximal complete subnetwork of order 3 or more.
- Cliques will tend to overlap, and the connected components of such overlapping cliques are considered
*social circles*. - Cliques are network "bones"; structure of overlapping cliques is network "skeleton".

- Cliques will tend to overlap, and the connected components of such overlapping cliques are considered
- Problem: Clique detection algorithm is slow. Therefore we instead search for complete subnetworks (without worrying about whether they're maximal).
- Triads: complete subnetworks of order 3 (triangles).
- Directed
- Undirected

- Pajek: set a model subnetwork as "First network", and network to analyze as "Second network", then Fragment (1 in 2), all in Nets menu. T