Computer Science, Spring 2008 CS249B “Science of Networks” Goals 
A high school dating network by Peter S. Bearman
et al, "The structure of
adolescent romantic and sexual networks", American Journal
of Sociology 110, 4491 (2004) .Males are red,
females are blue 

Instructor: Daniel Bilar (dbilar, x3093) Lectures: Monday and Thursday 1:302:40pm, SCI 270 Class Book: Csermely, P. (2006) , "Weak Links: Stabilizers of Complex Systems from Proteins to Social Networks", Springer Verlag, Berlin , ISBN 3540311513 Course homepage: http://cs.wellesley.edu/~cs249B Office hours: SCI E108, MW 34pm 

Ever wondered what comic book characters, the Powergrid, the Internet and Kevin Bacon have in common?
This course will give an overview of the theory and practice of complex networks. We will introduce basic concepts in network theory (graph and probability theory) , analyze scaling phenomena and power laws, discuss metrics, models, processes and algorithms, and use software analysis tools to experiment with realworld network data. Models of networks include random graphs, the smallworld model, preferential attachment, Pennock models, hierarchical networks and HOT processes. Real world networks we will study may include social/friendship networks , networks of the Internet (routers and WWW), comic book characters networks, transportation and ecological networks.
The course is open to all students, with no specific
background or major required. We will strive to explain the concepts as a
learning community in plain English, whenever possible.
Links for this class: Pajek (network analysis software) How to read
a scientific paper efficiently How to give a technical
presentation 
Other useful links for
this class: Pajek
tutorial
Pajek reference Tutorial on Graph Theory (required) Primer on Probability theory (required) Primer on Linear
Algebra (optional) Primer on Spectral Analysis of Networks (optional) Primer on Differential Equations (optional) 
Goals: This course has set of specific and general learning goals: First, we want to gain an understanding of the structure and properties of reallife networks, the processes that drive their formation, and the mathematical models that are used to analyze them. In parallel, we will acquire techniques and practices to negotiate technical, scientific papers  how to efficiently approach them, how to read graphs, how to deal stepbystep with unknowns. Lastly, our class narrative is partly metascientific, it is a science course about science, how it acquires, discusses, evaluates, corrects and evaluates. It is very instructive to see how the scientific paradigm unfolds in this nascent field
Students who take this class should be prepared to have the discipline to read and discuss a dozen papers; most are technical, and a few of them are lengthy. Furthermore, you will have to learn and assimilate basic probability theory quickly. Some calculus, linear algebra and differential equations is helpful in understanding all the math in the readings, but is not required for the course and does not affect evaluations. We will strive to explain the concepts as a learning community in plain English, whenever possible.
(major) Survey the etiology, structure and properties of reallife networks
(major) Understand and interpret analytical models of networks
(major) Efficiently read, negotiate, structure and absorb content of scientific, technical papers
(minor) Creative and interesting synthesis in the culminating project
(minor) Use various software tools to model and analyze networks
(minor) Present technical
concepts to an audience
Expectations: I will do my best to make the course interesting, worthwhile and pertinent to your education. You will have plenty of opportunities to show that me you are making progress. I will evaluate your work fairly and constructively and I will be of assistance in and out of class to help you reach these learning goals.
From you, if you choose to take this class, I will expect a commitment to your fellow students and to me. I will expect that you attend class regularly, prepared; that you will make an honest effort to grapple with and reflect on the material; that you will continuously identify problems you may have and find ways to overcome them, on your own and with my help.
Evaluations: There will be weekly closednotes quizzes (but no final exam), a couple of labs, and a culminating project with a class presentation.
Readings: The required book for the course is intended to give you a nonmathematical lively overview and introduction of the course topics. Peter Csermely is a very nice man, and he has told me that he is always eager to hear from students: You can mail him at csermely@puskin.sote.hu
You should to read his whole book as soon as possible. In addition, each week, on average, you will have to read roughly one or two papers.
Quizzes: Every week, their will be a short, in class, closedbook quiz on materials presented in prior lectures and in the readings. The quiz will be 1520 minutes and consist of 35 questions. These are not hard questions: If you attended class , did the assigned readings, and reflected upon them, you should have little problems with quiz questions.
Homework: There will be occasional small homework assignments.
Classroom activity: Before each class, I will expect you to hand in assigned homework/labs, do the assigned reading and review the material from the previous class. Since the new material will depend on what was previously covered, reviewing will help you as the course progresses. There will be many opportunities in class for discussion and you will not be able to participate if you do not review and keep up. During discussions, I do not expect you to read my mind when I ask questions, but I do expect you to try to give reasons for your answers. Nobody will be put down for incorrect answers or seemingly “stupid” questions – there are no power games in this class. We are a community of learners, me included.
Culminating Project: The culminating project may be completed in groups of two. It can take one of two forms:
1. A theoretical reaction paper, in which you read at least three topicrelated papers, at least one of which is not on the required reading list. You should then write approximately 58 pages in which you address the following points:
What is main technical content of the papers?
Why is it interesting in relation to one or more course topics?
What are the weaknesses of the papers, and how could they be improved?
What are some promising further research questions in the direction of the papers, and how could they be pursued?
The discussion should go beyond a mere summary of the papers. For instance, you might discuss some weaknesses in the papers, and suggest alternative approaches; formulate different hypotheses than the papers and suggest experiments that could be used to validate the hypotheses; discuss related work from a different field that the authors were not aware of, or a potential application of the work to a different field.
2. An empirical project, in which you experimentally evaluate an algorithm, a model, construct a program or measure on an interesting data set. You may program something, use Pajek/Matlab/Guess (or other types of suitable software). You will submit a report approximately 510 pages long.
For either form, you will submit a 1page proposal by the seventh week of classes. Format will be posted. Projects are subject to approval.
Student Presentations:
Everyone will give one presentation during the semester. The presentations will be about 20 minutes long. You will give a lecture to the class, including answering all questions from the class. It will be beneficial (but it is not required) for you to give a dry run of your lecture to me before you give it to the class. See the future handout Technical Presentations for advice on giving a good talk.
Attendance: You are expected to attend every class. If you are unable to make a class, please inform me of the reasons beforehand via email. Please make every effort to attend. Flagrant absenteeism will be noted. You are responsible for all information presented in class, whether or not you are there.
Collaboration and Academic Dishonesty: For a complete
discussion of my expectations, please read "Expectations of Working Together and Individually"
Exams and Grades: I do not curve, because it encourages grade jockeying and zerosum game mentality. If everyone achieves an A, that is fine with me. The course grade will be determined as follows:
Quizzes/Labs 
60% 
Projects 
20% 
Presentation 
10% 
Class participation 
10% 
The minimum grade you will receive is shown below. Grades may be raised and plusses or minuses added at my discretion.
Number 
Grade 
Meaning 
90100% 
A 
All major and minor goals achieved 
8089% 
B 
All major goals, most minor goals achieved 
7079% 
C 
All major goals, some minor goals achieved 
6069% 
D 
One major goal achieved, but student is not prepared for advanced work 
below 60% 
F 
None of the major goals achieved 
Learning strategies: Every course has effective ways of achieving mastery of the material. This course is no different. Among the strategies you should adopt are
Negotiate the readings smartly : Assiduously do the readings and use efficient techniques to negotiate the content. You will get a whole lot more out of the lecture; in addition, these techniques are completely general.
Cooperative learning: Explain the concepts in your own words to a fellow student, i.e. be a tutor to a tutee. This is so valuable I cannot stress it enough. By doing so you consolidate and integrate your own knowledge, and you learn a great deal about how to learn since you have to diagnose the tutee ’s learning problem in order to help him/her overcome it.
Experiment: Do not be shy to go to a computer and try out concepts mentioned in class and in the papers. You can use Java, C, Pajek, Ucinet, Guess, Matlab, Mathematica  whatever floats your boat and you are comfortable using.
Start your culminating project early.
This syllabus is subject to change. The authoritative version is always found on the CS 249B course homepage, http://cs.wellesley.edu/~cs249B
January 20^{th} 2008, Daniel Bilar (dbilar at wellesley dot edu)