# Questions tagged [social-networks]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
17 views

### Importance of an edge regarding distances

Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge. I am interested in the difference between the average ...
1 vote
114 views

### The modularity difference in Louvain algorithm for community detection in graphs

I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below. ...
1 vote
79 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 ...
1 vote
32 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 ...
151 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 ...
1 vote
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 ...
77 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 ...
392 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 ...
73 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, ...
305 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}$ ...
1 vote
32 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 ...
46 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 ...
1 vote
32 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. ...
310 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-...
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 ...
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 ...
260 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 ...
1 vote
213 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 ...
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 ...
1 vote
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 ...
94 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 ...
58 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 ...
314 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 ...
200 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, ...
215 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 ...
665 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 ...
2k 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 ...
159 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 ...
1 vote
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 ...
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 ...
1k 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 ...
184 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 ...
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 ...
169 views

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 ...