Large Structures Seminar: Darko Hric & Petteri Kaski
This talk is part of the AScI Thematic program "Challenges in Large Geometric Structures and Big Data" seminar. Check out our upcomning talks at https://aaltoscienceinst.github.io/lsbdseminar/.
| Where: | TUAS 3161 (AScI premises) |
| When: | 09.03.2015 @ 12.15 |
| Speaker: | Darko Hric & Petteri Kaski Aalto University |
| Title: | Large Structures Monday |
12:15 Darko Hric “Community detection in complex networks: structural versus annotated communities”
12:45 Petteri Kaski “An excursion into the edge-linear-time algorithms toolbox”
13:15 Discussion
Community detection in complex networks: structural versus annotated communities
Abstract: Detecting communities in networks is one of the most popular topics of network science. Despite this, a little is known about the structure of annotated communities (communities based on node annotations). While classical community detection algorithms use only connectivity and thus identify structural communities, it is often assumed that nodes grouped in this way share some common properties. This does not have to be true. My work is set out to investigate this connection: in which cases (and to what extent) will annotated communities correspond to the network structure.
An excursion into the edge-linear-time algorithms toolbox
Abstract: A fundamental goal in algorithm design for graph problems is to come up with algorithms whose running time scales as a linear function of the number of edges in the input graph. My intent is to review selected such designs for NP-hard problems that are fixed-parameter tractable (FPT); in particular, the exponential complexity of the problem can be isolated to a parameter of the input that is independent of the size of the graph.