Questions tagged [social-networks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
41 views

Efficient Network Clustering Algorithm for Million Node Networks

I am looking for a clustering algorithm that is scalable up to large sparse undirected, unweighted networks (10-40M nodes, 10-80M edges). The most important aspects I care about are scaling efficiency ...
user avatar
  • 215
0 votes
0 answers
40 views

Ranking messages on social media

People are always talking about "the algorithm" for social media platforms like Facebook and Twitter but I haven't yet seen a good explanation of what exactly these algorithms are actually ...
user avatar
1 vote
0 answers
29 views

Social Networking Disease Transmission

You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$ met at some point during ...
user avatar
0 votes
3 answers
102 views

Mutual Friends in a Network?

I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever). The problem statement is as such: If A and B are friends, and B and C are friends, then A and C are ...
user avatar
1 vote
0 answers
29 views

Reliability of information on large social networks like Wikipedia [closed]

I was going through the playlist of an online course on Social Network Analysis offered by the Indian Institute of Technology (Madras), when I came across the claim that "when a lot of people get ...
user avatar
0 votes
0 answers
72 views

How to minimize diffusion in undirected weighted graph

I've got a work that has to do with networks, where each edge has a weight ($w\in(0,1)$) and some random set of nodes are 'infected'. I don't know which nodes are (or how many). The diffusion spread ...
user avatar
  • 21
6 votes
2 answers
305 views

Algorithm for finding "mean center" of unweighted graph

I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does ...
user avatar
  • 215
2 votes
1 answer
64 views

Sampling in large graph using simple random walk

I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e, ...
user avatar
3 votes
2 answers
230 views

Correctness of the Betweenness centrality formula

Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is: $$\sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$ Where $\sigma_{st}$ ...
user avatar
  • 93
1 vote
1 answer
30 views

Analyzing the railways network [closed]

I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles ...
user avatar
2 votes
1 answer
42 views

(Formal) Proofs of Node Centrality Properties

Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to ...
user avatar
  • 23
1 vote
2 answers
30 views

Representing a network with two types of connections: A fishing application

I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together. ...
user avatar
2 votes
0 answers
271 views

What is the difference between multi-layer, multiplex and heterogeneous networks?

I know when we have multiple networks connected to each other, we can call every network a layer and the whole network is called multi-layer. But I don't know what is the difference between multi-...
user avatar
-3 votes
1 answer
121 views

How are optimal weights computed in best-Worst Multi-criteria Decision Making Method (Step 5 of BWM)? Can someone explain it with an example?

Title: Best-worst multi-criteria decision-making method Author:Jafar Rezaei, Pub: Omega 53 (2015) 49-57 BWMCD From this example How are optimal weights (W1*, W2* etc) computed on Page:22 ? what are ...
user avatar
  • 1
0 votes
0 answers
73 views

Facebook daily access time distribution

I'm trying to build an agent-based model to study facebook usage. One important part is determining, at each step, whether a given user is online/active or not. I am looking for a distribution of ...
user avatar
0 votes
1 answer
219 views

A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...
user avatar
1 vote
0 answers
167 views

Difference between Adjacency matrix and Laplacian matrix (Dynamical Process Perspective)

We can represent a simple connected graph $G$ using mathematically as adjacency matrix, $A$. There are other matrices related to the graph which is very useful is the Laplacian matrix $L=D-A$ where D ...
user avatar
10 votes
2 answers
2k views

social network graph problem

Here is the problem: There are connected graph with nodes representing a number of people. Each node/person has an opinion on a topic e.g. trump vs clinton, paper books vs kindle, etc The goal is ...
user avatar
  • 101
1 vote
0 answers
65 views

Identify community in a direct graph

I'm trying to identify communities in a direct graph. I only know how to use Spectral clustering and Girvan-Newman method but the both the methods work only with undirect graph. Am I wrong? So what ...
user avatar
  • 111
4 votes
2 answers
73 views

Is there a name for the problem of turning a bipartite graph into two graphs?

Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they ...
user avatar
0 votes
0 answers
56 views

Filter bubble algorithms for presenting related video lists

In a filter bubble, what are some of the techniques and best ways to determine the relationship between a video that is watched or liked, and the list of related videos to be presented to the browsing ...
user avatar
3 votes
1 answer
292 views

Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
user avatar
  • 33
4 votes
1 answer
198 views

Importance of a person to another person in social network

In social network (an unweighted indirect network), is there some measure of importance of a person A on another person B, ...
user avatar
7 votes
0 answers
202 views

Computing the "at least k friends in common" graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
user avatar
  • 2,209
3 votes
1 answer
631 views

Disconnecting a complete graph by removing edges randomly

Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph. I want to find out the minimum number of edges that I must remove ...
user avatar
5 votes
3 answers
1k views

Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution. The ...
user avatar
2 votes
0 answers
158 views

Sampling a Large Undirected Graph

I'm working with a very large undirected graph (a social network from a telecomunication company). I'm applying a clustering algorithm on this graph to find it’s most relevant communities. The ...
user avatar
1 vote
0 answers
110 views

Need an upper bound for node degree

I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the ...
user avatar
  • 131
2 votes
1 answer
3k views

find the minimum number of vertices in a directed graph from which the other vertices are reachable

In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met. (in other words all of the other vertices are reachable from these chosen vertices.) I want to ...
user avatar
  • 161
2 votes
0 answers
989 views

Looking for dynamic network data sets [closed]

There are a number of collections of network (or graph) data sets freely available on the web, e.g. http://snap.stanford.edu/data/index.html http://www.cc.gatech.edu/dimacs10/downloads.shtml I am ...
user avatar
  • 21
4 votes
2 answers
180 views

Empirical studies about benefits of Q&A sites for programming

I'm looking for empirical papers which investigate if a user can benefit from Q&A sites like Stack Overflow. I welcome any papers related to this topic, e.g: an experiment, investigating if a ...
user avatar
  • 151
3 votes
1 answer
1k views

What is the probability of friendship conditioned on the number of mutual friends

Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends? I am ...
user avatar
  • 21.7k
3 votes
2 answers
168 views

Analyzing Twitter Relationships

I'm not even sure if this is the right StackExchange to post this, but it seems like sentiment analysis would go here. What would be the best approach to determine if two people on Twitter are ...
user avatar
6 votes
1 answer
166 views

How to represent the interests of a Facebook user

I'm trying to figure out a way I could represent a Facebook user as a vector. I decided to go with stacking the different attributes/parameters of the user into one big vector (i.e. age is a vector of ...
user avatar
29 votes
4 answers
5k views

How to determine likely connections in a social network?

I am curious in determining an approach to tackling a "suggested friends" algorithm. Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. ...
user avatar
  • 621