Dima Verner's Journal
[Most Recent Entries]
[Calendar View]
[Friends View]
Monday, July 18th, 2005
| Time |
Event |
| 10:40a |
Сила связи Продолжение некоторых вопросов кластерного анализа ЖЖ. Важным понятием является сила связи. Представим, что есть кластер русских пользователей и кластер албанских пользователей ЖЖ. Достаточно одному русскому зафрендить албанца, и все становятся единым кластером. Связь это, однако, слабая - разрыв одного отношения френдования снова делает кластеры изолированными. Сила связи между двумя юзерами - это минимальное число отношений френдования, которые надо разорвать, чтобы нарушить связь. Пример. Юзеры A и B не связаны отношениями френдования. Однако, есть 10 юзеров, каждый из которых френдит и A, и B. Для того, чтобы разорвать дорожку от A до B, надо разрушить не менее десяти френдований. Более сложный пример. Юзеры A и B не связаны отношениями френдования, и у них нет общих френдов. Юзера A френдят 10 юзеров - a1, ..., a10; юзера B френдят 10 юзеров - b1, ..., b10. Имеется юзер C, который френдит 20 юзеров - a1, ..., a10, b1, ..., b10. Опять же, надо разрушить не менее десяти отношений френдования, чтобы уничтожить связь между A и B. Графически можно изобразить множество юзеров, соединенных линиями, толщина которых пропорциональна силе связи между юзерами. Далее, можно устанавливать порог силы связи. При обрыве всех линий толщиной 1 - какие-то юзеры отваливаются от кластера, кластер может разбиться на несколько изолированных, и т.д. Кластер, в котором все линии имеют толщину не менее 2 - кластер силы 2. Аналогично, вводим понятия "кластер силы 3", "кластер силы 4", и т.д. Уход отдельного поэта Не создает в пространстве брешь, - писал Игорь Иртеньев. В ЖЖ теоретически можно представить ситуацию, когда удаление одного ключевого юзера с большим количеством френдов и френд-оф нарушает связность. В примере выше удаление юзера C разбивает кластер силы 10 на два изолированных кластера A, a1, ..., a10, и B, b1, ..., b10. Вопрос для AT: какое количество ключевых юзеров надо удалить, чтобы разбить русский ЖЖ на два изолированных кластера сравнимой силы и размера (например, "либералов" и "патриотов")? | | 2:43p |
Расстояние Продолжение набросков к теории кластеризации ЖЖ, начало см. [ 1], [ 2]. Расстояние от юзера A до юзера B определяется тривиально: это длина минимальной цепочки френдования, соединяющей A и B. Введем дополнительные характеристики расстояния. Вес расстояния от A до B - это число отношений френдования, которые надо разрушить, чтобы цепочки данной длины от A до B не существовало. Если A является френдом B, а B не является френдом A, то расстояние между ними равно 1 с весом 1. Если A и B - взаимные френды, то расстояние между ними равно 1 с весом 2. Если A и B не связаны отношениями френдования, но есть 10 юзеров, каждый из которых френдит и A, и B, то расстояние от A до B равно 2 с весом в пределах от 10 до 20. Устойчивость расстояния от A до B - это число независимых цепочек данной длины от A до B, или число юзеров, которых нужно убить, чтобы цепочки данной длины от A до B не существовало. В примере выше расстояние от A до B равно 2 с устойчивостью 10. Другой пример. Юзеры A и B не связаны отношениями френдования, и у них нет общих френдов. Юзера A френдят 10 юзеров - a1, ..., a10; юзера B френдят 10 юзеров - b1, ..., b10. Имеется юзер C, который френдит 20 юзеров - a1, ..., a10, b1, ..., b10. Расстояние от A до B равно 4 с устойчивостью 1, так как разных независимых друг от друга цепочек, соединяющих A и B, нет - достаточно удалить одного юзера C, чтобы порвать связь. Контрольный вопрос: в последнем примере расстояние от A до B равно 4. [Ошибка: опрос #534753 не найден] | | 4:14p |
Best Places to Live 2005 MONEY magazine and CNN/Money spent months looking for Great American Towns -- where you would want to raise your children and celebrate life's milestones. Элликотт Сити вошел в американскую двадцатку. Все это, конечно, реклама продавцов недвижимости, но в целом я согласен - хороший городок. |
|