Networks and computational complexity

This is a general lecture of PhD student level:

The lecture discusses computational problems and their complexity with applications in the analysis of networks. It has has three mostly self-contained parts.

In the first part, the problem of finding network modules is discussed in some detail. A module is a group of nodes with many links among group members and relatively few links with others. In a social network, for example, modules may represent groups of people with similar interests. An optimal partition of a network into modules is an example of a difficult optimization problem, for which no efficient algorithm is known. The meaning of efficient is that the maximum (worst case) time for finding an exact solution is bounded by a polynomial in the size of the graph.

The second part deals with problems that can be solved efficiently (in
polynomial time) and some solution strategies. Greedy, dynamic
programming, local search and other fundamental types of algorithms are
outlined.

Finally, we take a glance at computational complexity theory, sketching
the importance of the "P versus NP" problem. P is the set of problems
that can be solved efficiently. NP contains all those for which a
proposed solution can be checked efficiently. P is a subset of NP. It
is an open question whether the inclusion is proper: Are there any
problems for which finding a solution is qualitatively more difficult
than checking it? The answer would have many implications, theoretical
(e.g. automatic mathematical proof construction) as well as practical
(safety of cryptography). "P versus NP" is one of the seven Millenium
Problems named by the Clay Mathematics Institute.
http://www.claymath.org/millennium/P_vs_NP/