کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435569 689915 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing maximal cliques in link streams
ترجمه فارسی عنوان
محاسبه کسرهای حداکثر در جریان لینک
کلمات کلیدی
پیوندهای جریان، شبکه های زمانی نمودارهای متغیر زمان کلایک، نمودارها، الگوریتم ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We introduce delta-cliques, that generalize graph cliques to link streams/time-varying graphs.
• We provide a greedy algorithm to compute all delta-cliques of a link stream.
• Implementation available on http://www.github.com/JordanV/delta-cliques.

A link stream is a collection of triplets (t,u,v)(t,u,v) indicating that an interaction occurred between u and v at time t. We generalize the classical notion of cliques in graphs to such link streams: for a given Δ, a Δ-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least once during each sub-interval of duration Δ. We propose an algorithm to enumerate all maximal (in terms of nodes or time interval) cliques of a link stream, and illustrate its practical relevance to a real-world contact trace.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 1, 4 January 2016, Pages 245–252
نویسندگان
, , ,